[C++] 백준 1260 DFS와 BFS

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

1260번: DFS와 BFS

 

1. 서론

 

DFS와 BFS의 완전 기초 문제인데... 범위 설정 잘못해서 계속 삽질했음 ㅠ.ㅠ

 

2. 문제 풀이

 

그래프가 주어진다. 그 그래프를 DFS로 탐색했을 때와 BFS로 탐색했을 때의 결과를 출력하는 문제이다.

조건은 탐색 시에 방문할 수 있는 경우가 여러 개인 경우 더 작은 숫자 먼저 탐색하는 것.

 

DFS와 BFS 코드는 블로그를 참조했다!! (스스로 짜는 게 좋긴 한데 생각도 안 나고 짜도 퀄리티 구릴 것 같아서)

 

DFS:

https://hongku.tistory.com/157?category=804730 

알고리즘 :: DFS 깊이 우선 탐색 (C/C++ 구현), 탐색 알고리즘

BFS:

https://hongku.tistory.com/156

알고리즘 :: BFS 너비 우선 탐색 (C/C++ 구현), 탐색알고리즘

 

이렇게 DFS, BFS 자체는 해결이 됐는데 작은 숫자를 먼저 방문하게 하기 위해서는 따로 처리가 필요했다.

 

이 문제를 입력받을 때 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호가 앞에 주어지고 연결된 간선의 두 정점이 주어진다.

이 순서가 정렬되어 주어지는게 아니라 랜덤 하게 주어진다. 그렇기 때문에 입력받을 때 작은 수가 먼저 들어갈 수도, 큰 수가 먼저 들어갈 수가 있기 때문에 입력을 받은 후에 각 배열들을 따로 정렬해준다.

 

나는 입력받을 때 정점의 최대 개수인 1001개의 배열로 이루어진 벡터를 선언했다. 그러니까 백터 배열을 만든 것인데 여기에 각 노드마다 이어진 상대방 노드의 값을 입력받는 것이다. 그리고 나중에 이 노드 배열을 정렬해서 작은 숫자들이 앞으로 오도록 만드는 것이다.

그런데 여기서 노드 숫자는 1부터 시작하는데 배열은 당연히 0부터 시작한다. 처음에는 착각해서 간선의 배수만큼 배열들을 정렬했는데 이것도 아니었고 정점의 개수만큼 반복문을 돌렸는데 이것도 아니었다. 결과적으로 <= 라고 써야 하는데 < 라고 써서 삽질을 엄청했다.

 

근데 진짜 웃긴점은 내가 처음에 간선의 개수만큼 배열을 정렬하고 서버에 돌리니까 out of bounds 에러가 나서 그냥 방문해야 하는 배열의 크기가 정점의 개수 1001개 아니라 10000으로 늘려도 안되길래 100000으로 늘렸더니 또 맞았다고 떠서 왜 그런지 몰라 골머리를 썩혔다. 왜 맞았는지는 아직도 모른다.... 그냥 정렬해야 하는 배열의 개수를 고치니까 1001로 다시 바꿔도 맞았다고 떴다. 진짜 미스터리^^,,

 

3. 코드 설명

 

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

using namespace std;

int visit[1001];
vector<int> a[1001];

void bfs(int s)
{
    queue<int> q;
    q.push(s);
    visit[s] = true;

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

        for (int i = 0; i < a[x].size(); i++)
        {
            int y = a[x][i];
            if (!visit[y])
            {
                q.push(y);
                visit[y] = true;
            }
        }
    }
}

void dfs(int s)
{
    if (visit[s]) return;

    visit[s] = true;
    cout << s << " ";
    
    for (int i = 0; i < a[s].size(); i++)
    {
        int x = a[s][i];
        dfs(x);
    }
}

int main()
{
    int n, m, v, i, x, y;

    cin >> n >> m >> v;

    for (i = 0; i < m; i++)
    {
        cin >> x >> y;

        a[x].push_back(y);
        a[y].push_back(x);
    }

    for (i = 0; i <= n; i++)
        sort(a[i].begin(), a[i].end());

    dfs(v);
    cout << endl;
    memset(visit, 0, sizeof(visit));
    bfs(v);
}

 

bfs 함수는 큐를 이용한다.

a 벡터 배열에는 n번째 배열에 n번 노드와 연결되어 있는 노드들의 값이 들어가 있다.

그걸 이용해 큐에 첫 번째로 방문하는 곳의 값을 넣고 그 n번째 배열에 들어가 있는 값들을 다 따로 방문하면서 방문했다고 표시한다. 

이렇게 탐색을 마치면 n번째 배열을 한 바퀴 돌며 탐색을 마치면 숫자 n을 큐에서 pop 한다. 즉 n번은 탐색이 끝난 것이다. 이를 더 이상 방문할 곳이 없을 때까지 반복한다. 

 

dfs 함수는 재귀를 이용한다. bfs가 순서대로 탐색을 했다면 dfs는 거리가 가까운 순으로 탐색한다고 보면 된다.

방문하려는 첫 번째 노드를 방문했다고 표시하고 그 n번째 노드에 있는 값들을 다시 dfs 함수를 호출해서 재귀적으로 방문한다.

이미 방문했으면 retuen, 아니면 배열에 방문했다고 true로 표시한다. 이것을 n개의 배열의 모든 값에 대해 보고 더 이상 방문할 곳이 없으면 함수가 끝나게 된다.

 

주의 사항!

위에서 말한 대로 숫자가 작은 순서대로 가야 하기 때문에 dfs, bfs 함수를 돌리기 전에 미리 입력받은 값들에 대해서 정렬이 필요하다.

그리고 visit 배열로 해당 정점들에 다 방문했는지 체크하는데 dfs, bfs 모두 같은 함수를 쓰기 때문에 한 번 사용 후에는 반드시 초기화해줘야 한다. (안 그러면 두 번째 함수를 사용했을 때 이미 다 방문한 것으로 체크되기 때문에.)