[백준] 1260번 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

솔직히 dfs는 이해 되었는데, bfs가 아직 이해가 되지 않았지만 최대한설명해보겠다. 

이번에는 코드부터 보는게 나을것 같다. 아직 bfs나 dfs를 설명하는데 어려움이 조금 있기 때문이다.

#include <bits/stdc++.h>
using namespace std;
int n,m,v;
int arr[1010][1010];
bool visit[1010];

void dfs(int v) {
  cout << v << " ";
  visit[v] = true;
  for(int i = 1;i<=n;i++) {
    if (visit[i] || !arr[v][i]) {
      continue;
    }
    dfs(i);
  }
}

void bfs(int start) {
  bool visit[10100] = {false};
  queue<int> q;
  q.push(start);
  visit[start] = true;

  while(!q.empty()) {
    int x = q.front();
    cout << x << " ";
    q.pop();
    for(int i = 1;i<=n;i++) {
      if (arr[x][i] && !visit[i]) {
        q.push(i);
        visit[i] = true;
      }
    }
  }
}
int main(void) {
  cin >> n >> m >> v;
  for(int i = 1;i<=m;i++) {
    int x,y;
    cin >> x >> y;
    arr[x][y] = 1;
    arr[y][x] = 1;
  }
  dfs(v);
  cout << "\n";
  bfs(v);
}
    

이 문제 같은 경우는 초기화에 신경써야 된다. 왜냐하면 dfs나 bfs나 같은 배열을 사용하기 때문이다. 뭐, 다른 배열로 만들어도 상관없을것 같다. 내가 bfs를 스택으로 풀려고 노력했는데, 실패했다. 시간도 시간이지만, 지금은 그냥 재귀로 풀었다. 

 

bfs이랑  dfs가 뭐가 다른지 설명하면 사실상 길찾는 건 똑같은데, 차이점이 분명이 존재한다. 

dfs가 모두다 아다시피 깊이 우선 탐색이다. 깊이 우선 탐색에 왜 굳이 스택혹은 재귀를 사용하는 이유는 스택(재귀)의 특성을 잘 생각해보면 된다.

이 둘은 먼저 나오는게 나중에나오는 FILO방식으로 되어있다. 그렇기 때문에 노드를 방문할때마다 값을 추가해주면 자연스럽게 값은 밑으로 들어간다. 그러니까 깊어지게 된다는 뜻이다. 물론, 다른 자료구조로 이것을 구현할 수 있으면 상관없다. 비슷한예로 큐도 마찬가지다. 그럼 여기서 의문이 생길지도 모른다. 어째서 1부터 4까지 입력하고 이것 스택에 넣으면 무조건 1 2 3 4가 나와야 하는데, 왜 다르게 나올까?(물론 같게 나올 수는 있습니다. ) 이유는 값이 들어가기 전에 탈출을 시키기 때문이다. 이를 활용하면 스택의 괄호 문제를 해결할 수 있다.(물론 어렵지만...)

 

이제 코드를 설명하면

노드에 방문하면 값을 true로 둔다. 또 값이 지정한 값이라면 지나갈 수 있게 하면 된다. 

그리고 항상 방문했다는 걸 알려주면 된다.

 

마지막으로 arr[x][y] = arr[y][x]인 이유는 문제에 양방향이라고 나와 있기 때문에 이렇게 하였다.

이제 이를 활용해서 문제를 풀어야 하는데.... 

참고로 bfs에 visit를 초기화한 이유는 이거 안해주면 이미 통과된거라 나오기 때문에 이렇게 하였다. 또, init메서드를 만들 수 도 있는데 귀찮아서 만들지 않았다.

 

int v,e,st;
vector<int> adj[1001];
bool vis[1001];

void dfs(int cur){  
  cout << cur << ' ';
  for(int i = 0; i < adj[cur].size(); i++){
    int nxt = adj[cur][i];
    if(vis[nxt]) continue;
    vis[nxt] = true;
    dfs(nxt);
  }
}

void bfs(){
  queue<int> q;
  q.push(st);
  vis[st] = true;
  while(!q.empty()){
    int cur = q.front();
    cout << cur << ' ';
    q.pop();
    for(int i = 0; i < adj[cur].size(); i++){
      int nxt = adj[cur][i];
      if(vis[nxt]) continue;
      q.push(nxt);
      vis[nxt] = true;
    }    
  }
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> v >> e >> st;
  while(e--){
    int a,b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  for(int i = 1; i <= v; i++)
    sort(adj[i].begin(), adj[i].end());
  vis[st] = true;
  dfs(st);
  cout << '\n';
  fill(vis, vis+v+1,false);
  bfs();
}