[백준/C++] 1260번 : DFS와 BFS

문제

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

입력

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

출력

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

 

풀이

https://dev-minji.tistory.com/76

[개념] DFS와 BFS

 

// 1260번 DFS와 BFS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 10001

int N, M, V; // 정점 개수, 간선 개수, 시작 정점
vector<int> graph[MAX]; // 인접 행렬 그래프
bool isVisited[MAX] = {false, }; // 정점 방문 여부
queue<int> q;

// DFS : 방문한 노드에서 아직 방문하지 않은 인접한 노드로 옮겨가는 식
void DFS(int v){
  isVisited[v] = true; // 방문 표시
  cout << v << " ";

  for (int i=0; i<graph[v].size(); i++){
    int next = graph[v][i];
    // 방문하지 않은 경우
    if (isVisited[next] == false)
      DFS(next); // 재귀함수 호출
  }
}

// BFS : 방문한 노드로부터 아직 방문하지 않은 인접한 모든 노드를 큐에 추가하는 방식
void BFS(int v){
  q.push(v); // 루트 노드 삽입
  isVisited[v] = true;

  while(!q.empty()){
    int cur = q.front();
    q.pop();
    cout << cur << " ";

    for (int i=0; i<graph[cur].size(); i++){
      int next = graph[cur][i];
      // 방문하지 않은 경우
      if (isVisited[next] == false){
        // 큐에 넣어주고 방문했음을 표시
        q.push(next);
        isVisited[next] = true;
      }
    }
  }
}

int main(){
  queue<int> q; // BFS용
  cin >> N >> M >> V;

  for (int i=0; i<M; i++){
    int u, v;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  // sort : 하나의 정점에서 다음을 탐색할 떄 node에 순차적으로 접근해야 함
  for (int i=0; i<MAX; i++){
    sort(graph[i].begin(), graph[i].end());
  }

  DFS(V);
  cout << "\n";

  fill_n(isVisited, MAX, false); // 방문 여부 초기화
  BFS(V);
}