쌍문동 척척박사
Spring / ReactJS / PS

BFS와 DFS

BFS와 DFS

[BOJ] 2178 미로 탐색

위 문제는 전형적인 DFS/BFS 문제다. 왜 그럴까? 다음 그림을 보면 이해가 된다.

2.gif

칸이라는 개념을 없애고 연결 관계만을 파악해 노드의 개념으로 나타내니 그래프 형태가 된다. 이제 우리는 해당 문제를 그래프의 특성만 뽑아내 그래프에서의 최단거리 문제로 변형해 풀 수 있게 된다. 우리는 그 중 가장 유명한 그래프 탐색 알고리즘인 BFS와 DFS에 대해 알아볼 것이다.

기본 개념

우선 DFS (Depth-First Search)는 말 그대로 깊이를 우선시하는 기법이다. 따라서 같은 level 또는 depth에 있는 다른 노드들은 고려하지 않고, 계속해서 이동을 진행하다가 목적지에 도착하면 그때 백트래킹하며 다른 노드들을 통한 경로도 탐색하게 된다.

3.gif

반대로 BFS (Breadth-First Search)는 너비를 우선시하는 기법이다. 같은 depth에 있는 노드들을 먼저 쭉 훑으며 목적지가 아니라면 그 다음 depth의 노드들로 이동한다.

4.gif

그럼 다음과 같이 일반적인 그래프가 주어졌을 때 최단 경로를 찾아야 한다면 어떤 알고리즘이 더 적합할까?

3.png

우선 DFS부터 살펴보자.

4.png

한 경로를 선택해 가장 먼저 목적지에 도착한 경우다. 그럼 이때 우리는 이 경로가 최단 경로임을 단언할 수 있는가? 답은 No이다. 그럼 최단 경로임을 보장하려면 어떻게 해야하나? 바로 완전 탐색 (Brute Force)을 해서 모든 경로를 다 방문하면서 그 중 최단 경로를 선정해야 한다.

5.png

이번엔 BFS를 살펴보자.

6.png

같은 depth에 있는 모든 노드들을 훑으며 진행하다가 한 경로가 목적지에 도착한 경우다. 이때 우리는 최단 경로임을 단언할 수 있는가? 답은 Yes이다. 그 이유는 현재 모든 경로가 같은 depth를 유지하고 있는데, 우리가 구하는 최단 경로의 거리는 depth에 의해 결정되기 때문이다.

그렇기에 그 뒤에 다른 어떤 경로가 목적지에 도착하더라도 그 경로는 현재 경로보다 거리가 같거나 더 길다는 것이 보장되기 때문에 의미가 없다. 따라서 이 문제에서는 BFS가 더 적합한 풀이가 된다. 그럼 이제 직접 코드를 작성해보자.

DFS

DFS는 보통 재귀를 통해 구현하는 것이 가장 쉽다. 하지만 파이썬의 경우 재귀의 depth가 깊어지면 오버플로가 발생할 수 있으므로 오버헤드를 낮추기 위해 반복문으로 구현하기도 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.io.*;
import java.util.*;

class Pot {
    int r, c, d;
    public Pot(int r, int c, int d){
        this.r = r;
        this.c = c;
        this.d = d;
    }
}
class Solution {
                    // 동 서 남 북
    final int[] dr = { 0, 0, 1, -1 };
    final int[] dc = { 1, -1, 0, 0 };
    final int MAXN = 100 + 2;
    
    int N, M;
    int[][] board = new int[MAXN][MAXN];
    boolean[][] visit = new boolean[MAXN][MAXN];
    
    public int dfs(Pot pot){
        if(pot.r == N && pot.c == M){
            return pot.dist;
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < 4; i++){
            int nr = pot.r + dr[i];
            int nc = pot.c + dc[i];
            
            if(nr < 0 || nr >= N || nc < 0 || nc >= M)  continue;
            if(visit[nr][nc])   continue;
            if(board[nr][nc] == 0)  continue;
            
            visit[nr][nc] = true;
            min = Math.min(min, dfs(new Pot(nr, nc, pot.d+1)));
            visit[nr][nc] = false;
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    public Solution() {
        // after input
        visit[0][0] = true;
        System.out.println(dfs(new Pot(0,0,0)));
    }
}

참고

여기서 방향전환 테크닉을 처음 보는 사람이 있을 것 같아 설명을 첨부하겠다. 한 칸에서 다른 칸으로 갈 수 있는 방향의 개수는 동서남북 4개다. 일반적인 방법으로는 if문을 4번 써서 분기를 나누고 중복 로직을 수행해 해당 방향으로 나아간다. 하지만 이 테크닉에서는 우리가 진행해야 할 방향을 nr, nc라는 배열에 저장한다. 그리고 해당 nr, nc를 활용해 다음 방향을 설정하는 파트는 다음 코드다.

1
2
3
4
for(int i = 0; i < 4; i++){
    int nr = pot.r + dr[i];
    int nc = pot.c + dc[i];
}

우리가 현재 위치인 (r,c)에서 동쪽으로 한 칸 가려면 (r,c+1)이 되야 한다. 즉, r과 c에 더해져야 하는 수는 각각 (0,1)이다. 그래서 우리는 (dr[0],dc[0])을 각 좌표에 더해주면 다음 좌표가 된다. 이번엔 북쪽으로 한 칸 갈 때는 (r-1,c)이 되야 하므로 (dr[3],dc[3]) = (-1,0)을 더해준다. 이제 이해가 될 것이다.

이 테크닉은 개인적으로 기업 테스트를 볼 때마다 60% 이상의 확률로 활용 문제가 나올 정도로 중요한 테크닉이라 생각한다.

BFS

BFS는 큐를 이용해 구현한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.*;
import java.util.*;

class Pot {
    int r, c, d;
    public Pot(int r, int c, int d){
        this.r = r;
        this.c = c;
        this.d = d;
    }
}
class Solution {
                    // 동 서 남 북
    final int[] dr = { 0, 0, 1, -1 };
    final int[] dc = { 1, -1, 0, 0 };
    final int MAXN = 100 + 2;
    
    int N, M;
    int[][] board = new int[MAXN][MAXN];
    boolean[][] visit = new boolean[MAXN][MAXN];
    
    public int bfs(){
        Queue<Pot> q = new ArrayDeque<>();
        q.offer(new Pot(0,0,0));
        visit[0][0] = true;
        
        while(!q.empty()){
            Pot pot = q.poll();
            if(pot.r == N && pot.c == M){
                return pot.d;
            }
            for(int i = 0; i < 4; i++){
                int nr = pot.r + dr[i];
                int nc = pot.c + dc[i];
                
                if(nr < 0 || nr >= N || nc < 0 || nc >= M)  continue;
                if(visit[nr][nc])   continue;
                if(board[nr][nc] == 0)  continue;
                
                q.offer(new Pot(nr,nc,pot.d+1));
                visit[nr][nc] = true;
            }
        }
        return -1;
    }
    public Solution() {
        // after input
        System.out.println(bfs());
    }
}

참고 1

하지만 각 edge마다 길이 가중치가 달랐다면 Dijkstra Algorithm을 사용해야 했을 것이다.

참고 2

여기까지만 보면 왠지 BFS가 더 효율적인 알고리즘처럼 보인다. 하지만 다음 문제들만 보면 DFS가 더 효율적이게 된다. 두 알고리즘에서 절대적인 우위는 없다.

그런데 가끔 보면 BFS를 써도 되고, DFS를 써도 되는 문제가 나오는데, 어떤 상황에서 두 알고리즘 모두 비슷한 성능을 갖게 되는 것일까? 답은 완전 탐색을 해야 할 때이다. 이유는 곰곰히 생각해보자.

대회 기출

사실 대회 문제를 일일히 언급할 필요도 없이, 백준에 있는 삼성 SW 역량 테스트 기출 문제삼성 A형 기출 문제 문제집만 봐도 기업들에서 얼마나 탐색 문제를 좋아하는지 알 수 있다. 따라서 해당 문제집들을 풀면서 탐색 기법을 익히면 될 것 같다. 그래도 혹시 해당 난이도가 아직까지는 어렵다면 추가 문제들을 먼저 풀고나서 풀어보자.

추가 문제

comments powered by Disqus