그래프와 BFS(Graph & Breadth First Search)

BFS(너비 우선 탐색) 알고리즘에 대해 알아보기 전에 필수적으로 알아봐야 할 자료구조는 바로 그래프(Graph)다. 그래프는 실질적으로 프로그래밍 언어 라이브러리 상에서 제공하기 보다는 추상적인 자료구조로써 개념을 차용하여 알고리즘에 응용하여 푸는 경우가 많으므로, 자료구조 카테고리가 아닌 알고리즘 카테고리에서 함께 다루고자 한다.

---

그래프

그래프의 정의 및 개념

그래프(G)는 정점 집합(V)과 간선 집합(E)으로 구성된 자료구조로, 대상과 대상 간의 관계를 나타내는 자료구조다.

그래프는 다들 너무나도 익숙하게 들어봤을 '쾨니히스베르크(Königsberg) 다리'를 보고 수학자 오일러가 '한붓그리기' 문제를 해결하기 위해 고안한 것으로 알려져 있기도 하다. 이 고안법에서 중요한 것은, 각 육지를 잇는 다리를 육지들의 관계이자 하나의 간선(edge)로 봤다는 것과, 다리를 통해 이어지는 각 육지들은 하나의 노드이자 정점(vertex)으로 봤다는 점이 중요하다.

이미지 출처: https://suhak.tistory.com/54

이러한 접근법을 우리 일상에도 대입해본다면, 각기 다른 문제, 상황 등을 정점으로 보고 연결고리를 간선으로 처리한다면 상관관계를 서로 만들어 낼 수 있을 것이다. 

그래프의 종류

먼저, 방향성에 따라서 그래프는 크게 '방향 그래프(directed graph)'와 '무방향/무향 그래프(undirected graph)'로 분류할 수 있다. 이름에서 직관적으로 알 수 있다시피, 방향 그래프는 간선에 방향의 개념이 들어가 있는 것을 의미한다. 실세계에서의 개념으로는 '일방통행', '부모/자식 관계' 등이 있을 수 있다.

반면, 무방향 그래프의 경우 두 정점이 관계가 있는가만을 표현하는 것으로, 두 정점간의 관계가 없다면 간선을 연결하지 않게 된다.

두 정점을 연결하는 간선이 두 개 이상인 경우가 있을수도 있는데, 이는 '다중 그래프(multi graph)'라고 한다.

 

또한, 각 정점을 연결하는 간선에서 비용이 발생할 수 있다. 고속도로라고 가정한다면 통행료가 그 예시가 될 것이다. 이렇게 간선에 가중치가 부여된 그래프를 '가중 그래프(weighted graph)'라고 한다.

 

이외에도 그래프의 각 요소 및 경로에 관한 추가적인 명칭들이 부여되기도 하는데, 이는 아래 정리 항목을 통해서 살펴보자.

 

그래프 용어 정리

• 방향 그래프: 간선의 방향이 유의미한 그래프
• 무방향 그래프: 간선의 방향이 무의미한 그래프
• 다중 그래프: 두 정점 쌍이 간선을 여러 개 가질 수 있는 그래프
• 가중치 그래프: 두 정점을 잇는 간선에 가중치가 부여된 그래프
• 경로: 두 정점을 잇는 간선의 열
• 루프: 한 정점에서 자신으로 연결되는 간선
• 사이클: 시작점과 끝점이 동일한 경로
• 인접: 두 정점이 간선으로 연결되어 있는 경우

---

너비 우선 탐색(BFS, Breadth First Search)

그래프 탐색 알고리즘에서 가장 큰 두 축을 차지하고 있는 것이 바로, '깊이 우선 탐색(DFS, Depth First Search)'과 '너비 우선 탐색(BFS, Breadth First Search)'이다. 이외에도 가중치 그래프를 다루는 '다익스트라(Dijkstra)', '프림 알고리즘(Prim's Algorithm)', '크루스칼 알고리즘(Kruskal Algorithm)'을 비롯하여, 트리 형태의 탐색을 다루는 '최소 스패닝 트리' 등이 있지만 이번 시간 그리고 다음 시간에 다룰 BFS와 DFS에 그 기반을 두고 있으므로 기초를 잘 다룰 필요가 있다.

(일반적으로 서적이나 알고리즘을 다루는 블로그들에서 DFS를 먼저 다루는 경우가 많지만, BFS를 먼저 다루는 이유는 순전히 필자가 BFS를 좋아하기 때문이다.)

 

사실 DFS의 경우 다음 포스트에서 다룰 예정이지만 재귀를 통해 풀이하는 경우가 많으므로 다소 직관적이지 않다는 면이 있어서, 보다 직관적으로 그래프 탐색을 다룰 수 있는 BFS에 대해 먼저 다루기로 한다. 예시 그래프를 통해서 BFS의 동작 개념을 이해해보자.

다음과 같은 그래프가 주어졌을 때, A 노드에서 I 노드까지 가는 최단 경로를 구하고 싶다고 가정해보자. 먼저, 출발점(A)에서 몇 개의 간선을 통해야 다른 노드들로 갈 수 있는지를 기반으로 그래프를 재배열할 수 있다. 시작점으로부터 그래프를 따라가면서 각 노드에 도달할 수 있는 최소 경로의 길이를 각자만의 방식으로 분류해보자. 

• 0: A
• 1: B, C, G
• 2: D, E, F
• 3: H
• 4: I

E 노드의 경우 {(A, B), (B, E)} 경로를 통해 두 번만에 도달할 수 있으므로, {(A, C), (C, D), (D, E)}라는 길이 3의 경로를 통해 간 경우, E는 이미 방문한 적 있는 노드이므로 배제하고 생각한다. 아래 그림을 통해 출발점을 기준으로 정리된 그래프를 보자.

각자 첫 번째 그래프를 보고 노드에 도달하는 최소 길이를 정리한 방식을 되짚어서 생각해보자. 누군가는 A에 인접한 모든 노드들을 순차적으로 방문해보면서, 방문할 경우 길이를 미리 기입했을 수도 있을 것이고, 또 누군가는 A에 연결된 3개의 간선 중 하나의 간선을 선택해 쭈욱 따라가봤을 수도 있다. 전자의 경우 BFS를 적용한 것이고 후자의 경우 DFS를 적용하여 최단 경로를 찾아냈다고 볼 수 있다.

 

전자의 방식을 되짚어 보면 너비 우선 탐색(BFS)의 경우, 각 노드를 방문할 때마다 모든 인접한 노드들을 먼저 검사하는 것이다. 이 중 처음 방문한 노드를 발견하면, 방문 예정이라고 기록해 둔 뒤 별도의 위치에 저장해둔다. 인접한 노드를 모두 검사하고 나면, 저장된 목록에서 다시 순차적으로 정점을 꺼내서 방문하게 된다. 즉, BFS의 실행 순서를 결정하는 것은 어떤 노드를 먼저 방문할지 저장하는 '저장 목록'에 의해 결정되는 것이다. 위 그래프에서 A를 방문했다면 저장 목록에는 '(B, C, G)'가 추가될 것이다. 이 중 'B'를 방문할 경우, '(E, F)'가 목록에 추가되지만, '(E,F)'는 '(C, G)' 노드가 방문되기 이전에 먼저 방문되서는 안된다. 

 이를 구현하기 위한 가장 간단한 방법은 FIFO, 즉 'Queue'를 사용하는 것이다. 우리는 순차적으로 노드를 임시로 저장하기 위해 `큐(Queue)`를 사용할 것이지만 만약 우선순위가 별도로 존재할 경우 `우선 순위 큐(PriorityQueue)`를 선택할 수도 있을 것이다.

 

BFS의 경우, DFS와는 다르게 최단 경로 문제를 푸는데만 사용된다. 최단 경로의 경우 위 예제처럼 두 노드를 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제로, 실질적으로도 미로나 특정 경우의 수를 만들기 위한 가장 빠른 방법을 탐색하는 등의 문제로 주로 출제가 되는 편이다.

 

백문이 불여일견, 예제 문제를 통해 BFS의 개념을 조금 더 익혀보자.

---

BFS 예제

2178번: 미로 탐색

 

사실 얼핏 개념만 소개해놓고 바로 들어가기에는 문제의 난이도가 다소 있을 수도 있다.

하지만, 아래 코드를 순차적으로 따라가며 2차원에서는 어떻게 BFS가 동작하는지 익혀보자. 예제 문제의 가이드라인만 코드에 주석으로 기재하였다. BFS의 개념에 대해 이해했다면 디테일한 설명보다는 실제로 코드를 따라가 보는 것이 개인적으로 가장 빠르게 습득할 수 있었기 때문이다.

public class bfs_2178_searchMaze {

    // 네 방위(북, 동, 남, 서)로 이동하기 위한 좌표 설정
    static final int[] dy = {-1, 0, 1, 0};
    static final int[] dx = {0, 1, 0, -1};
    
    // 입력 받은 2차원 배열
    static char[][] map;
    
    // 방문한 노드를 재방문하지 않기 위한 플래그 배열
    static boolean[][] visit;

    static int solve(int N, int M) {
        Node start = new Node(0, 0);

        Queue<Node> q = new LinkedList<>();
        q.add(start);
        visit[0][0] = true; // 방문한 노드 처리

        int length = 0;
        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                Node now = q.poll();
                
                // 최종 방문 노드에 도달한 경우 return 처리
                if (now.y == N - 1 && now.x == M - 1) {
                    return length + 1;
                }

                for (int dir = 0; dir < 4; dir++) {
                    // 이동할 방향 좌표 계산
                    int ny = now.y + dy[dir];
                    int nx = now.x + dx[dir];

                    // 이동할 수 없는 방향에 대한 처리
                    if (ny < 0 || nx < 0 || N <= ny || M <= nx || visit[ny][nx] || map[ny][nx] == '0') continue;

                    // 다음 방문 노드에 대한 처리
                    q.add(new Node(ny, nx));
                    visit[ny][nx] = true;
                }
            }

            length++;
        }

        return length;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        map = new char[N][M];
        visit = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
        }

        bw.write(solve(N, M) + "");
        bw.flush();
        bw.close();
        br.close();
    }

    static class Node {
        int y, x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

}

---

참고문제

1. [Silver 2] DFS와 BFS
BFS를 다루었지만 간접적으로 다룬 DFS의 개념도 한 번 상상하여 풀어보자.

1260번: DFS와 BFS

2. [Silver 1] 숨바꼭질
정점과 간선 개념을 응용하여, 다른 유형의 문제를 BFS로 풀어본다.

1697번: 숨바꼭질

3. [Gold 4] 빙산
BFS를 이용하여 구역의 개념을 풀어본다.

2573번: 빙산