[백준 / BOJ] C++ 1260 DFS와 BFS

1260번: DFS와 BFS

 

문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

풀이

dfs와 bfs의 기본 사용 방법을 연습할 수 있는 문제다. 간선이 양방향이므로 x, y를 입력받아 graph[x][y] = 1, graph[y][x] = 1로 해준다.

 

시작 정점부터 dfs를 돌리면 방문처리를 한 후 정점에서 연결된 위치가 아직 방문하지 않았다면 해당 정점으로 dfs를 다시 진행한다. 이를 반복하여 계속해서 가능한 끝까지 탐색한 후 돌아와 다시 다음 정점을 확인하는 방식이다.

 

이후 모든 방문 처리를 취소하고 bfs를 진행한다. 시작 정점을 방문처리 한 후 큐에 넣는다. 큐가 비어있지 않은 동안, 큐의 front인 정점에서 이동할 수 있는 모든 점들을 방문처리하고 큐에 추가하는 과정을 반복한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, v;
vector<vector<int>> graph(1001, vector<int>(1001, 0));
vector<bool> visited(1001, false);

void dfs(int start) {
  visited[start] = true;
  cout << start << ' ';
  for (int i = 1; i <= n; i++)
    if (graph[start][i] == 1 && !visited[i])
      dfs(i);
}

void bfs(int start) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  cout << start << ' ';
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = 1; i <= n; i++)
      if (graph[x][i] == 1 && !visited[i]) {
        q.push(i);
        visited[i] = true;
        cout << i << ' ';
      }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m >> v;
  while (m--) {
    int x, y;
    cin >> x >> y;
    graph[x][y] = 1;
    graph[y][x] = 1;
  }
  dfs(v);
  cout << '\n';
  for (int i = 1; i <= n; i++)
    visited[i] = 0;
  bfs(v);
  return 0;
}