[백준 1260] DFS와 BFS (C#, C++) - soo:bak

문제 링크

1260번 - DFS와 BFS

설명

하나의 그래프가 주어졌을 때, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 순서를 출력하는 문제입니다.

그래프는 양방향이며, 정점 번호는 1부터 시작합니다.

탐색 규칙은 다음과 같습니다:

• 방문 가능한 정점이 여러 개라면 정점 번호가 작은 순서대로 방문합니다.
• DFS는 한 방향으로 깊이 들어가며 재귀적으로 탐색하고,
• BFS는 큐를 이용하여 인접한 정점을 넓게 확장해가며 탐색합니다.

탐색 결과는 시작 정점부터 방문된 순서를 공백으로 구분하여 출력해야 합니다.

접근법

먼저, 입력으로 주어지는 간선을 통해 인접 리스트를 구성합니다.

양방향 그래프이므로, 두 정점 모두에 서로를 추가해주어야 합니다.

DFS 탐색:

• 방문한 정점을 바로 출력하며, 재귀적으로 다음 정점으로 이동합니다.
• 이미 방문한 정점은 다시 방문하지 않도록 하며,
• 정점 번호가 작은 순서대로 방문하기 위해 인접 리스트는 오름차순 정렬합니다.

BFS 탐색:

• 큐를 이용하여 현재 정점에서 인접한 정점들을 순차적으로 방문합니다.
• 먼저 들어간 정점이 먼저 나오는 구조로,
• 역시 방문한 정점은 다시 큐에 넣지 않도록 관리합니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
  static List<int>[] adj;
  static bool[] visited;

  static void DFS(int v) {
    visited[v] = true;
    Console.Write($"{v} ");
    foreach (var u in adj[v]) {
      if (!visited[u]) DFS(u);
    }
  }

  static void BFS(int start) {
    var queue = new Queue<int>();
    visited = new bool[adj.Length];
    visited[start] = true;
    queue.Enqueue(start);

    while (queue.Count > 0) {
      int v = queue.Dequeue();
      Console.Write($"{v} ");
      foreach (var u in adj[v]) {
        if (!visited[u]) {
          visited[u] = true;
          queue.Enqueue(u);
        }
      }
    }
  }

  static void Main() {
    var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
    int n = input[0], m = input[1], start = input[2];

    adj = new List<int>[n + 1];
    for (int i = 1; i <= n; i++)
      adj[i] = new List<int>();

    for (int i = 0; i < m; i++) {
      var edge = Console.ReadLine().Split().Select(int.Parse).ToArray();
      adj[edge[0]].Add(edge[1]);
      adj[edge[1]].Add(edge[0]);
    }

    for (int i = 1; i <= n; i++)
      adj[i].Sort();

    visited = new bool[n + 1];

    DFS(start);
    Console.WriteLine();
    BFS(start);
    Console.WriteLine();
  }
}

C++

#include <bits/stdc++.h>

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef queue<int> qi;

int numInit;
vvi adj;
vi visited;

void dfs(int s) {
  if (visited[s]) return;

  if (s != numInit) cout << " ";
  visited[s] = 1;

  cout << s;
  for (int u : adj[s])
    dfs(u);
}

void bfs() {
  qi q;
  visited.assign(visited.size(), 0);
  visited[numInit] = 1;

  q.push(numInit);
  while (!q.empty()) {
    int s = q.front(); q.pop();
    if (s != numInit) cout << " ";

    cout << s;
    for (int u : adj[s])
      if (!visited[u]) {
        visited[u] = 1;
        q.push(u);
      }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int cntNode, cntEdge; cin >> cntNode >> cntEdge >> numInit;
  adj.resize(cntNode + 1);
  for (int i = 0; i < cntEdge; i++) {
    int node1, node2; cin >> node1 >> node2;
    adj[node1].push_back(node2);
    adj[node2].push_back(node1);
  }

  for (auto& row : adj)
    sort(row.begin(), row.end());

  visited.resize(cntNode + 1);

  dfs(numInit);
  cout << "\n";
  bfs();
  cout << "\n";

  return 0;
}