[백준][1260] DFS와 BFS (C++)

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

1260번: DFS와 BFS

개인적으로 제일 어려워하는 종류인 BFS/DFS를 새로 공부하자는 의미에서 기본문제부터 다시 풀어봤습니다. 처음 알고리즘 공부 시작할 때는 기본 문제조차도 다른 사람의 풀이를 보지 않으면 풀지 못했는데 이제는 이 정도 문제는 따로 풀이를 보지 않아도 풀 수 있는 정도는 된 것 같아 조금 뿌듯합니다 ㅎㅎ

 

DFS와 BFS 성공

문제

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

입력

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

출력

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

 

---

정점과 간선, 탐색 시작점을 입력으로 받으면 DFS로 탐색한 순서, BFS로 탐색한 순서를 출력하는 기본문제입니다. 정점과 간선, 탐색 시작점을 전역 변수로 받고 방문한 노드를 표시한 배열은 DFS와 BFS로 탐색할 때 구분하기 위해 visit_dfs[1001], visit_bfs[1001]로 따로 저장했습니다. 문제에서 표시할 정점의 범위가 1부터 1000까지이기 때문에 배열은 1001로 선언해주었습니다. 

 

#include <iostream>
#include <queue>
using namespace std;
 
bool graph[1001][1001]; // 노드 사이에 간선이 있음을 표시할 2차원 배열 
bool visit_dfs[1001]; // dfs로 탐색할 때 표시할 방문한 노드 
bool visit_bfs[1001]; // bfs로 탐색할 때 표시할 방문한 노드 
 
int N, M, V; // 정점과 간선, 탐색 시작 노드를 전역 변수로 선언 
 
void dfs(int n){
    cout << n << " ";
    
    visit_dfs[n] = true; // 방문한 노드 표시 
    
    for(int i = 1; i <= N; i++){
        if(graph[n][i] && !visit_dfs[i]){ // 탐색할 노드와 간선이 존재한다면 재귀함수 호출 
            dfs(i); // dfs는 스택으로 구현되기 때문에 재귀함수 호출 
        }
            
    }
    return;
}
 
void bfs(){
    queue<int> q;
    q.push(V); visit_bfs[V] = true; // 큐에 먼저 탐색을 시작할 노드를 넣어 줌 
    
    while(!q.empty()){ // 큐가 비어있다면 탐색이 끝난 것 
        int n = q.front(); cout << n << " ";
        q.pop();
        for(int i = 1; i <= N; i++){ // 제일 앞의 노드에 대해서 간선이 존재하는 노드를 큐에 모두 넣어줌 
            if(graph[n][i] && !visit_bfs[i]){
                q.push(i);
                visit_bfs[i] = true; // 큐에 넣어둔 노드는 방문했다는 표시를 해준다
                // 방문한 표시를 큐에서 뺄 때 해주면 나중에 같은 노드가 큐에 중복으로 들어가는 상황이 생긴다 
            }
        }
    }
}
 
 
int main(){
    cin >> N >> M >> V;
    int n, m;
    
    for(int i = 0; i < M; i++){
        cin >> n >> m;
        graph[n][m] = true;
        graph[m][n] = true;
    }
    
    dfs(V);
    cout << "\n";
    bfs();
}