[알고리즘] 코드로 알아보는 DFS 알고리즘

1. DFS

DFS는 (Depth-First Search) 깊이 우선 탐색이다. 그래프에서 한 경로를 끝까지 탐색한 후 돌아와서 다른 경로를 탐색하는 방식이다. 노드와 간선으로 구성된 그래프나 트리에서 사용된다.

 

아래의 그림을 보면서 '깊이 우선 탐색'이 뭔지 알 수 있다. 깊이 있게 그래프를 탐색하고 다시 돌아와서 다른 간선의 방문하지 않은 노드를 깊이있게 탐색하는 것을 반복하는 것이다.

첫번째 탐색

두번째, 세번째 탐색

 

2. DFS 유형

그렇다면 어떠한 경우에 DFS를 사용할까! 경로 탐색이나 가능한 모든 경우의 수를 조사하는 완전 탐색에 자주 사용된다.

예를 들어, 아래와 같은 문제를 풀면 파악할 수 있다.

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

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

 

3. 코드로 살펴보는 DFS

1) Python

def dfs(r, c):
    print(graph[r][c])
    visited[r][c] = True

    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    for dr, dc in directions:
        next_r = r + dr
        next_c = c + dc

        if 0 <= next_r < len(graph) and 0 <= next_c < len(graph[0]):
            if not visited[next_r][next_c]:
                dfs(next_r, next_c)


graph = [[1, 6, 3, 4], [3, 6, 9, 8], [9, 2, 3, 4]]
visited = [[False for _ in range(len(graph[0]))] for _ in range(len(graph))]
dfs(0, 0)

 

2) Java

public class Main {
    static int[][] graph = {{1, 6, 3, 4}, {3, 6, 9, 8}, {9, 2, 3, 4}};
    static boolean[][] visited;
    public static void main(String[] args) {
        visited = new boolean[graph.length][graph[0].length];
        dfs(0, 0);
    }

    public static void dfs(int r, int c) {
        System.out.println(graph[r][c]);
        visited[r][c] = true;

        int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        for (int[] direction : directions) {
            int next_r = r + direction[0];
            int next_c = c + direction[1];

            if (next_r >= 0 && next_r < graph.length && next_c >= 0 && next_c < graph[0].length) {
                if (!visited[next_r][next_c]) {
                    dfs(next_r, next_c);
                }
            }
        }
    }
}

 

 

DFS 문제를 풀기위해서는 DFS 알고리즘의 특징을 정확하게 파악하는 것이 중요하다.!