Algorithm - DFS/BFS (깊이우선탐색, 너비우선탐색)

들어가기 전에

대학교 알고리즘 수업 때 DFS, BFS를 배우면서 뭔 말인지는 대충 알겠는데 뭔가 별로 쓰일 것 같지도 않고, 정확하게 공부하자니 어려워서 딱 “필요한 만큼”만 공부했다. 그 때 확실히 끝냈더라면 DFS, BFS와 관련된 PS 문제를 수월하게 풀었을텐데, 후회했다. 이제 책을 보며 다시 정리하고 예제를 풀어보려 한다. 탐색 알고리즘은 정말 중요하고, 활용도가 높다. (이번 부스트캠프 2020 2차 마지막 문제를 못 푼 것이 정말 아쉽다, 제대로 공부 해놓을걸.)

DFS, 깊이 우선 탐색

DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프의 기본 구조에서 두 노드가 간선으로 연결되어 있다면 ‘두 노드는 인접 adjacent하다고 말한다.

사실 이런 설명을 보고 한번에 이해하면 진작에 탐색 알고리즘은 마스터했을 것이다. 나는 구글에서 DFS, BFS 글들을 아무리 검색해도 완벽하게 이해되지 않았는데, 책에 나온 코드를 보며 한 줄씩 따라가니 이해하기 쉬웠다. 코드를 먼저 보자.

def dfs(graph, v, visited):
    visited[v]=True
    print(v, end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False]*len(graph)
dfs(graph, 1, visited)

실행 결과

1	1 2 7 6 8 3 4 5

생각보다 기본적인 dfs 함수 틀 자체는 복잡하지 않게 생겼다. 재귀를 사용하는데 dfs는 스택, bfs는 큐이고 재귀 함수 자체가 기본적으로 스택이기 때문에 편하게 재귀를 사용한다. (안 쓰는 방법도 있고, 구현하는 방법은 정말 많다)

graph를 보면 왠 숫자들의 배열이 배열로 감싸져 있는데, 그 전에 그래프를 표현하는 방식은 크게 2가지가 있다.

인접 행렬(Adjacency Matrix) 방식
- 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
인접 리스트(Adjacency List) 방식
- 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장하는 방식

따라서 코드의 graph는 인접 리스트 방식으로 저장되어 있다. 1번 노드부터 8번 노드까지 차례대로 연결된 노드를 나타낸 것이다. 0번 노드는 없기 때문에 빈 배열로 자리만 차지하게 둔다.

이제 방문하는 노드마다 visited를 True로 표시하며 탐색을 시작한다. graph에 노드마다 연결된 노드들이 있으므로 for문으로 순회하며 방문하지 않은 노드들을 차례로 dfs를 재귀 호출하며 방문한다.

방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.

결론적으로 DFS는 차례대로 정렬된 노드를 방문하며 그 인접 노드들을 재귀적으로 방문하는 것이다.

BFS, 너비 우선 탐색

BFS는 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드, BFS는 제일 가까운 노드부터이다. 큐 자료구조를 이용하는 것이 정석인데, 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되기 때문이다.

알고리즘의 작동 방식은,

탐색 시작 노드를 큐에 삽입 -> 방문 처리
큐에서 노드를 꺼내고 그 노드의 인접노드 중 방문하지 않은 노드를 모두 큐에 삽입 -> 방문 처리
전 과정을 수행할 수 없을 때까지 반복

코드를 보자.

from collections import deque

def bfs(graph, start, visited):
    q=deque([start])
    visited[start]=True
    
    while q:
        v=q.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i]=True
    
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False]*len(graph)
bfs(graph, 1, visited)

큐 자료구조를 이용하므로 효율을 위해 파이썬에서는 deque를 사용한다. 첫 방문 노드를 queue에 삽입하고 방문처리 후, 인접 노드를 모두 큐에 넣고 하나씩 빼면서(popleft()) 방문처리하는 과정을 큐가 빌 때까지 반복한다.

DFS, BFS에 관련된 예제를 하나씩 풀어보자.

DFS - 음료수 얼려 먹기

0과 1로 이루어진 N*M의 배열에서 0 묶음의 개수(연결된 0의 묶음 개수)를 구하는 문제이다.

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def dfs(x,y):
    if x<=-1 or x>=n or y<=-1 or y>=m: return False
    if graph[x][y]==0:
        graph[x][y]=1
        for i in range(4):
            dfs(x+dx[i],y+dy[i])
        return True
    return False
                
n,m=map(int, input().split())
graph = [list(map(int,input())) for i in range(n)]

result=0
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            result+=1

print(result)

상, 하, 좌, 우로 탐색하므로 dx, dy로 이동 방향을 미리 정해주면 나중에 사용하기 편하다. 특정 지점의 상, 하, 좌, 우를 탐색한 후 인접 노드 중 값이 0이면서 아직 방문하지 않은 노드를 방문하고, 방문한 노드에서 다시 상, 하, 좌, 우를 탐색하며 방문을 진행하면 모든 노드를 방문할 수 있다.

BFS - 미로 탈출

0과 1로 이루어진 배열에서 1로만 갈 수 있는 길의 방문 순서를 1, 2, 3.. 으로 기록하여 최종적인 방문 순서를 구하는 문제이다.

from collections import deque

dx=[-1,1,0,0]
dy=[0,0,1,-1]

def bfs(x,y):
    q=deque()
    q.append((x,y))
    
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx, ny=x+dx[i], y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m or graph[nx][ny]==0: continue
            if graph[nx][ny]==1:
                graph[nx][ny]=graph[x][y]+1
                q.append((nx,ny))
    return graph[n-1][m-1]

n,m=map(int, input().split())
graph = [list(map(int,input())) for i in range(n)]

print(bfs(0,0))

맨 처음에 (1,1)의 위치에서 시작하며, (1,1)의 값은 항상 1이라고 문제에 언급되어 있다. 시작 좌표에서 상, 하, 좌, 우로 탐색하고, 1인 값의 노드가 있다면 2로 바꾼다. 위 과정을 반복하면 최단 경로의 값들이 1씩 증가하는 형태가 된다.