[백준 1260번/C언어] DFS와 BFS, Queue로 풀이

백준 1260번 문제를 큐(Queue)로 풀어보았습니다. 

백준 1260번: https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

문제 내용은 아래와 같습니다. 

 

 

 DFS와 BFS에 대해서는 이전에 자료구조를 공부할 때 스택과 큐를 공부하며 코드를 구현해본 적이 있는데요, 그 때는 지금 문제와는 달리 일방향 그래프에 대해서 구현을 해서 아예 코드를 다시 작성했습니다. 이전에 일방향 그래프로 구현한 코드도 추후에 기회가 된다면 업로드 하도록 하겠습니다. 

 

 우선 DFS와 BFS가 무엇인지 간단히 설명하고, 문제 풀이로 넘어가겠습니다. DFS와 BFS는 둘 다 그래프 탐색(Graph Traversal)의 방법입니다. 그래프는 간단히 말하면 간선으로 연결된 노드들의 구조 정도로 생각할 수 있습니다. 이어서 DFS와 BFS에 좀 더 초점을 맞춰 설명하면, DFS는 Depth-First Search의 약자로, 말그대로 깊이를 우선시하여 탐색하는 방식입니다. 처음 시작하는 노드에서 간선으로 연결된 다른 노드에 들어가서 그 노드에서 다시 연결된 노드로 들어가기를 반복해서 끝까지 탐색한 후, 다시 처음 노드에 연결된 다른 노드에 들어가서  같은 과정을 반복한다고 생각하면 됩니다. BFS는 Breadth-First Search의 약자로, 너비를 우선시하여 탐색하는 방식입니다. 이 방식의 경우 처음 시작하는 노드에 연결된 노드를 먼저 다 탐색한 뒤, 다시 해당 노드에 연결된 노드에 들어가는 방식입니다. 말로 이해하는 것보다 그림으로 이해하는 게 간편한 개념이라서 아래 그림으로 DFS와 BFS를 비교해보았습니다. 

 아래 그림은 위 문제에 예제 입력1을 표현한 것입니다. 가장 왼쪽에 있는 그래프는 위 예제 입력을 그래프로 표현해두었습니다. 양방향 그래프이기 때문에 양방향 화살표로 표현했고, 가장 먼저 접근해야 하는 노드가 1이기 때문에 동그라미를 그려놓았습니다. 빨간색 화살표로 표현한 것이 DFS인데, 앞서 언급한 것처럼 '깊이'를 우선시 해야하기 때문에 1에 연결된 2로 접근하고 2에 연결된 4에 접근하고 4에 연결된 3에 접근하고 다시 원래 1로 가야하지만 1을 이미 읽었기 때문에 탐색을 멈추게 됩니다. 가장 오른쪽, 노란색으로 표현된 그림이 BFS인데, '너비'를 우선시 해야하기 때문에 1의 인접 노드인 2와 3을 먼저 읽고, 다시 먼저 읽은 2로 가서 2의 인접 노드인 4를 읽고, 노드를 모두 읽었으므로 탐색을 마치게 됩니다. 

 

 

 이제 DFS와 BFS를 구현한 코드를 보려 합니다. 메인 함수는 실행과 문제 조건을 받기 위한 함수이고, DFS() 함수가 DFS를 위한 함수이며, traverse() 함수와 BFS() 함수가 BFS를 위한 함수입니다. 그리고 전역변수인 connect, visitedDFS, visitedBFS를 선언했는데, connect는 노드들의 연결 정보를 포함한 2차원 배열이고, visitedDFS는 DFS 과정에서 해당 노드를 방문했는지 여부를 표시한 배열입니다. visitedBFS의 경우는 BFS 과정에서의 방문 여부를 나타내는 배열입니다. 방문 여부를 나타낸 배열의 경우, 0으로 초기화되어있기 때문에 방문하면 1로 바꿔주는 방식을 택했고, 노드들의 연결 정보를 담을 connect 배열 역시 노드 a와 노드 b를 연결하는 간선이 존재한다면 connect[a][b]와 connect[b][a] 모두 1이 되도록 했습니다. 

 공간 효율성을 위해서는 malloc을 사용하여 필요한 만큼만 메모리를 할당해주는 게 좋지만, 전역변수를 사용한 이유는 너무 많은 과정이 추가되기 때문이었습니다. 따라서 문제에서 제시한 최대값을 줘서 전역변수로 배열을 선언했습니다. (실제로 malloc 사용을 시도하다가 포기했습니다. 메모리를 할당할 경우 0으로 모두 초기화해주는 과정부터, 2차원 배열이 있어 malloc도 반복문을 써서 하나하나 해줘야 하고, malloc 체크도 해줘야 하는 등 번거로왔습니다. 그리고 함수를 여러개 사용하는 만큼 모든 함수에서 사용 가능한 전역변수를 사용하는 편이 훨씬 편하게 느껴졌습니다.) 하지만 만약 입력 가능한 최대값이 극단적으로 크거나 제시되어 있지 않은 경우, 혹은 메모리 효율이 중요한 경우는 malloc을 사용해주는 편이 낫습니다. 백준의 경우 보통 메모리 효율보다는 시간 효율이 중요하기 때문에 보다 적은 단계로 편하게 활용 가능한 전역변수를 사용했습니다. 

 

 전역변수 때문에 설명이 길어졌는데, 우선 가장 간단히 이해 가능한 메인 함수를 보면, 입력에서 주어지는 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V를 입력받은 후, 간선의 개수(M)만큼 반복하는 반복문을 통해 연결된 노드 정보를 입력받습니다. 여기서 주의할 점은 간선 정보를 받을 때 꼭 양방향으로 정보를 저장해줘야 한다는 것입니다. (즉, 1 3을 받는다고 하면 connect[1][3]과 connect[3][1] 모두를 꼭 1로 만들어줘야 합니다.) 문제에서 제시했듯 간선이 양방향이기 때문입니다. 그리고 DFS와 BFS를 각각 실행시키면 끝납니다.

 DFS부터 살펴보면, DFS() 함수를 재귀함수로 설정해서 탐색을 수행합니다. 처음 시작할 노드인 v와 정점의 개수 n을 인자로 받는데, v의 값을 바꾸면서 재귀를 수행하게 됩니다. v가 아직 방문하지 않은 노드인 경우에만 프린트해주고, 방문한 노드로 표시해줍니다. 그 이후 모든 노드들을 반복문으로 탐색하면서 만약 v와 연결되어 있는 노드이면서 아직 방문하지 않은 노드라면 해당 노드를 v로 만들어 DFS를 다시 실행해줍니다.

 BFS를 보면 BFS() 함수와 traverse()라는 helper function이자 recursive function을 사용합니다. 우선 BFS에서 처음 방문해야 하는 v를 queue에 담아준 후 head를 0, tail을 1로 초기 설정하여 traverse 재귀를 시작해줍니다. head가 tail과 같거나 그보다 크면 queue가 비어있다는 뜻이므로 재귀를 종료해야 합니다. 그렇지 않다면 현재 탐색하는 노드로 queue내 head 위치에 있는 노드를 설정해줍니다. queue는 선입선출 개념을 가지고 있으므로, head에 있다는 뜻은 결국 가장 먼저 들어왔다는 뜻이고, 그래서 먼저 꺼내준다고 생각하면 됩니다. 그리고 head 위치를 다음으로 옮겨줍니다. 만약 현재 탐색 중인 노드인 cur을 이미 방문했다면 바로 queue에 저장된 다음 노드로 넘어갈 수 있도록 traverse() 함수를 다시 실행해주고, 방문하지 않았다면 현재 노드를 출력한 후 현재 노드의 인접 노드를 queue에 담는 과정을 수행해줍니다. BFS과정에서 역시 queue 배열의 크기를 현재 경우에 딱 맞게 선언하지는 않았습니다. 우선 주어진 정점의 개수를 초과할 수 있어서 넉넉한 공간이 필요했고, 모든 요소를 0으로 초기화해주는 과정을 피하려는 의도였습니다. 

#include <stdio.h>

int connect[1001][1001];
int visitedDFS[1001];
int visitedBFS[1001];

void DFS(int v, int n) {
    if (!(visitedDFS[v])) {
        printf("%d ", v);
        visitedDFS[v] = 1;
        for (int i = 1; i <= n; i++) {
            if (connect[v][i] && !(visitedDFS[i]))
                DFS(i, n);
        }
    }
}

void traverse(int n, int head, int tail, int queue[1000]) {
    if (head >= tail)
        return;
    
    int cur = queue[head++];
    if (!(visitedBFS[cur])) {
        printf("%d ", cur);
        visitedBFS[cur] = 1;
        for (int i = 1; i <= n; i++) {
            if (connect[cur][i] && !(visitedBFS[i]))
                queue[tail++] = i;
        }
    }
    traverse(n, head, tail, queue);
}

void BFS(int v, int n) {
    int queue[1000000];
    queue[0] = v;
    traverse(n, 0, 1, queue);
}

int main() {
    int N, M, V;
    scanf("%d %d %d", &N, &M, &V);
    
    int a, b;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &a, &b);
        connect[a][b] = 1;
        connect[b][a] = 1;
    }
    
    DFS(V, N);
    printf("\n");
    BFS(V, N);
}

 

 

 그래프, 스택, 큐 등의 자료구조에 대한 이해만 있다면 어렵지 않게 풀 수 있는 문제이나, 관련된 개념이 잡혀있지 않을 경우 막막할 수 있습니다. 인터넷에도 좋은 글이 많으니 관련된 공부를 먼저 하고 접근하기를 추천합니다.