[백준 알고리즘/BOJ] 1260번 DFS와 BFS(C++)

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

이번 글은 백준 알고리즘 1260번 DFS와 BFS C++ 입니다.

소스 코드에서 주석을 보면 쉽게 이해가 될 것입니다.

 

1. 문제

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

 

 

2. 입력

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

 

 

3. 출력

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

 

 

4. 소스 코드

#include
#include
#include

using namespace std;
#define MAX 1001 // 입력에서 N이 1<=N<=1000 이라서 1001로 기준

int n, m, start; // n : 정점의 개수, m : 간선의 개수, start : 시작할 정점의 번호
int A[MAX][MAX]; // 인접행렬의 값을 받기 위한 행렬
int visit[MAX]; // 방문했던 것을 체크하기 위한 플래그 배열 dfs에서 방문시 1 미방문 0, bfs에서는 visit 배열을 그대로 사용하려 하니까 반대로 사용하면 됩니다.


void dfs(int start); 
void bfs(int start);

int main()
{
    cin >> n >> m >> start;
    int x, y;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        A[x][y] = A[y][x] = 1; // [1][2]의 인접행렬의 값은 [2][1]과 같기 때문
    }
    dfs(start);
    cout << "\n";
    bfs(start);
    return 0;
}

void dfs(int start)
{
    cout << start << ' '; // 첫 start 정점 번호 출력
    visit[start] = 1; // 방문 하였으므로 visit[start] = 1로 방문 체크
    for (int i = 1; i <= n; i++) // 정점의 갯수대로 반복문을 돌면서 방문을 했거나 인접행렬에 0이 있으면 지나가                                                    고, dfs(i) 재귀
    {
        if (visit[i] == 1 || A[start][i] == 0) continue;
        dfs(i);
    }
}

void bfs(int start)
{
    queue q;  
    q.push(start); // 첫 queue에 있는 값 push
    visit[start] = 0; // dfs에서 사용한 visit 배열을 반대로 사용하면 된다.
    
    while (!q.empty()) { //queue가 빌 때까지 while문
        start = q.front(); //
        cout << start << ' ';
        q.pop();
        for (int i = 1; i <= n; i++)
        {
            if (A[start][i] == 0 || visit[i] == 0) continue;
            q.push(i);
            visit[i] = 0;
        }
    }
}

 

 

6. 결과