[알고리즘] 깊이 우선 탐색 (+LeetCode 200)

BFS (너비 우선 탐색) 와 비슷하게  tree/graph 구조에서 조건을 만족하는 node를 찾을 때 사용하는 알고리즘이다  (2023.03.05 - [분류 전체보기] - [알고리즘] 너비 우선 탐색 (+LeetCode 733)).

DFS (Depth First Search, 깊이 우선 탐색) 는 말 그대로 깊이부터 탐색하는 알고리즘. 위에 tree를 보면 이해하기 쉽다. 우선 1번 노드부터 출발해서 다음과 같은 순서로 탐색을 한다:
1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 7

보다시피 깊이 방향으로 먼저 끝까지 탐색을 하는 방식으로 탐색을 하기 때문에 깊이 우선 탐색이다.

 

이러한 알고리즘은 recursive (재귀) 하게 구현할 수도 있고 stack을 사용해서 구현할 수도 있다.

우선 recursive 방식부터 pseudo code를 살펴보자. G는 graph/tree, v는 node라고 생각하면 된다.

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

G를 위 그림의 tree라고 가정하고 v를 1로 두면  1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 7 순서로 탐색하는 것을 알 수 있다

 

이제  stack을 사용한 구현 방식을 보자. Stack은 last in first out queue라고 생각하면 된다 (가장 나중에 들어온 원소가 가장 먼저 빠져나가는 구조). Stack은 Python에서 list의 append / pop으로 구현 가능하다.

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)

재귀 함수와 비슷하지만 탐색하는 순서가 다르다. 위 그림같은 경우 탐색 경로는 다음과 같다: 1 -> 4 -> 7 -> 3 -> 2 -> 6 -> 5

 

BFS 와 DFS tree / graph 구조에서 서치 하는 것은 비슷하지만 문제의 조건에 따라 선택해야 효율적으로 풀 수 있다. 

• 답이 root node에서 멀지 않으면 BFS가 좋다
• Tree가 넓으면 BFS는 너무 많은 메모리를 잡아먹을 수도 있다
• 등등

간단한 문제를 풀면 알고리즘 이해에 도움이 될 것이다.

Number of Islands - LeetCode

문제 간단 설명: '1', '0' 으로 이뤄진 grid가 있을 때 상하좌우가 모두 '1'연결되어 있는 영역을 땅, 상하좌우가 '0'으로 연결되어 있는 영역을 물이라고 하자. 이때 섬의 수를 구하는 것이 문제.

 

우선 재귀 함수로 구현해보자:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        h, w = len(grid), len(grid[0]) # 높이와 너비
        def dfs(i,j): # 우선 dfs 함수 구현
            if i < 0 or i >= h or \ 
                j < 0 or j >= w or \
                grid[i][j] != '1':
                return # (i,j)가 grid 밖/물이면 중단
            grid[i][j] = '0' # 방문 했다고 등록
            dfs(i+1,j) # 이제 상하좌우 탐색
            dfs(i,j+1)
            dfs(i-1,j)
            dfs(i,j-1)
        
        count = 0 # 섬의 수
        for i in range(h):
            for j in range(w):
                if grid[i][j]=='1':
                	count += 1 # 땅을 찾았으니 섬 수 증가
                    dfs(i,j) # dfs 시작
                    
        return count

설명: grid를 전체 탐색하는데, 땅을 찾으면  우선 섬의 수를 1 증가하고, 그 지점부터 dfs 를 한다. dfs를 실행하면 시작점부터 좌우상하 탐색을 하며, 땅인 지점들을 다 물로 바꿔버린다. 이렇게 grid를 모두 탐색하면 grid는 다 '0'으로 바뀌고 섬의 수를 구할 수 있다.

 

이제 stack으로 구현해 보자. stack으로 구현한 것 빼고 위 풀이와 아이디어는 같다.

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        h, w = len(grid), len(grid[0])
        stack = []
        directions = [(0,1), (1,0), (0,-1), (-1,0)] # 좌우상하
        count = 0 # 섬의 수
        for i in range(h):
            for j in range(w):
                if grid[i] [j] == '1':
                    count += 1 # 땅을 찾았으니 섬의 수 증가
                    # dfs 시작
                    grid[i][j] == '0' # 시작점 탐색 완료 표시
                    stack.append((i,j))
                    while stack:
                        cur_pos = stack.pop()
                        for direction in directions: # 좌우상하 탐색
                            next_pos = (cur_pos[0] + direction[0], cur_pos[1] + direction[1])
                            if 0 <= next_pos[0] < h and \
                                0 <= next_pos[1] < w and \
                                grid[next_pos[0]][next_pos[1]] == '1':
                                grid[next_pos[0]][next_pos[1]] = '0'
                                stack.append((next_pos)) # grid 내부이고 땅이면 탐색 완료 표시 후 stack에 추가
        return count

 

Refs:

https://en.wikipedia.org/wiki/Depth-first_search
https://stackoverflow.com/questions/3332947/what-are-the-practical-factors-to-consider-when-choosing-between-depth-first-sea