1260: DFS와 BFS

어떤 문제인가?

BFS, DFS를 적용하는 문제.

시행착오 횟수

2번, 그리고 시중에 나온 정답도 참고함.

1차 시도: TE

처음에는 아래와 같이 짰는데, 그 당시에는 무슨 이유인지를 몰라 해멨었다.

#include <stdio.h>

int queue[10001], adj[1001][1001], dfs_visited[1001], bfs_visited[1001], queue_head=0, queue_tail=0, N;

void dfs(int n) {
    if(dfs_visited[n] == 1) return;
    printf("%d ", n);
    dfs_visited[n] = 1;

    for(int i=1; i<=N; i++) {
        if(adj[n][i] == 1)
            dfs(i);
    }
}

void bfs(int n) {
    if(bfs_visited[n] == 1) return;
    queue[queue_tail++] = n;

    while(queue_head < queue_tail) {
        int current = queue[queue_head];
        if(bfs_visited[current]) {
            queue_head++;
            continue;
        }

        for(int i=1; i<=N; i++) {
            if(adj[current][i] == 1)
                queue[queue_tail++] = i;
        }

        bfs_visited[current] = 1;
        queue_head++;
        printf("%d ", current);
    }
}

int main() {
    int M, V;
    scanf("%d%d%d", &N, &M, &V);

    for(int i=0; i<M; i++) {
        int src, dst;
        scanf("%d%d", &src, &dst);
        adj[src][dst] = 1;
        adj[dst][src] = 1;
    }

    dfs(V);
    printf("\n");
    bfs(V);
}

2차 시도: AC

그래서 시중에 나온 답안을 참고했다.
아뿔싸! 나는 바보같게도 DFS를 할 때 필요없는 재귀 가지를 만들고 있었다.

void dfs(int n) {
    if(dfs_visited[n] == 1) return;
    printf("%d ", n);
    dfs_visited[n] = 1;

    for(int i=1; i<=N; i++) {
        if(adj[n][i] == 1)
            dfs(i);
    }
}

dfs_visited를 이용한 건 좋은데, 그 과정에서 넘겨도 되는 함수 호출을 굳이 하고 있었고, 이것이 아마 성능에 악영향을 끼쳤을 것이다. 당장 인접 행렬을 쓰기 때문에, 최악의 경우에는 1000 $\times$ 1000번의 계산을 해야 하는데 거기에다 함수 호출까지 하면 BFS를 할 시간이 없다.
-> 사실이 아니다. 수정 문단을 참고하자.

BFS의 경우에는 재귀를 쓰지 않음에도 불구하고 쓸데 없는 코드가 들어갔었다. 답안과 참고하여 다음과 같은 코드를 제출해 정답 처리를 받았다.

#include <stdio.h>

int queue[10001], adj[1001][1001], dfs_visited[1001], bfs_visited[1001], queue_head=0, queue_tail=0, N;

void dfs(int n) {
    printf("%d ", n);
    dfs_visited[n] = 1;

    for(int i=1; i<=N; i++) {
        if(adj[n][i] == 1 && dfs_visited[i] != 1)
            dfs(i);
    }
}

void bfs(int n) {
    queue[queue_tail++] = n;
    bfs_visited[n] = 1;
    printf("%d ", n);

    while(queue_head < queue_tail) {
        int current = queue[queue_head++];

        for(int i=1; i<=N; i++) {
            if(adj[current][i] == 1 && bfs_visited[i] != 1) {
                queue[queue_tail++] = i;
                printf("%d ", i);
                bfs_visited[i] = 1;
            }
        }
    }
}

int main() {
    int M, V;
    scanf("%d%d%d", &N, &M, &V);

    for(int i=0; i<M; i++) {
        int src, dst;
        scanf("%d%d", &src, &dst);
        adj[src][dst] = 1;
        adj[dst][src] = 1;
    }

    dfs(V);
    printf("\n");
    bfs(V);
}

문제를 풀 때 주의해야 할 것

처음에 '무방향 그래프'임을 모르고 그래프의 한 방향만 지정해줬다. 무방향 그래프라면 아래처럼 양방향임을 나타내줘야 한다.

        adj[src][dst] = 1;
        adj[dst][src] = 1;

수정

코드를 살짝 달리하여, 2차 시도 코드의 dfs 구현을 다음과 같이 바꿔보았다.

void dfs(int n) {
    if(dfs_visited[n] == 1) return;
    printf("%d ", n);
    dfs_visited[n] = 1;

    for(int i=1; i<=N; i++) {
        if(adj[n][i] == 1)
            dfs(i);
    }
}

그런데 이 코드는 맞았습니다! 를 받았다. 그렇다면 BFS 구현에 문제가 생긴 것이다.
어떤 문제가 있었는지는 추후에 확인해봐야겠다.. 지금은 시간이 좀 많이 지났다.