[C++] 백준 1260 - DFS와 BFS

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

1260번: DFS와 BFS

<알고리즘 분류>

   -  그래프 탐색(Graph Search)

   -  너비 우선 탐색(Breadth-First Search)

   -  깊이 우선 탐색(Depth-First Search) 

 

<풀이> 

  1. DFS와 BFS의 기본 개념을 잘 이해하고, 이를 코드에 적용할 수 있는지를 스스로 판단할 수 있는 대표적인 좋은 문제다. 

  2. 문제에서 시키는 대로, DFS와 BFS 코드 공식을 활용해서 풀어내면 된다. 

 

<주의사항>

  1. DFS는 재귀 함수(Recursion Function)를 이용한다. visited배열을 통해 방문한 노드를 체크하고, 검증한다.

  2. BFS는 큐(queue)를 이용한다. 현재의 점과 연결되어 있는지와 방문 여부를 확인하고, 그에 따라 queue에 push한다.

   

<코드>

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
int graph[1001][1001] = {0,};
queue<int> q;
int visited[1001];
int N;

int reset(){
    for (int i=0; i<=1000; i++)
    {
        visited[i] = 0;
    }
    return 0;
}

void dfs(int start){
    visited[start] = true;//현재 점과 연결돼있고 방문되지 않았으면 visit 하기. 그리고 재귀 !
    cout << start << " ";
    
    for (int i=1; i<=N; i++)
    {
        if(graph[start][i] == 1 && !visited[i])
            dfs(i);
    }
    
}

void bfs(int start){
    q.push(start);
    visited[start] = true;
    cout << start << " ";
    while (!q.empty()){
        //큐에 값이 있을 경우 반복 실행.
        // 큐에 값이 있다는 것은? 아직 방문하지 않은 노드가 있다! 
        int x = q.front();
        q.pop();
        
        for (int i=1; i<= N; i++) // 현재의 점과 연결돼있고 방문되지 않은 노드면 push
        {
            if(graph[x][i] && !visited[i])
            {
                q.push(i);
                visited[i] = true;
                cout << i << " ";
            }
        }
        
    }
}

int main(){
    int  M, V, A, B;
    cin >> N >> M >> V;
    
    for (int i=0; i<M; i++)
    {
        cin >> A >> B;
        graph[A][B] = 1;
        graph[B][A] = 1;
    }
    
    reset();
    dfs(V);
    cout << "\n";
    reset();
    bfs(V);
    
}