DFS/BFS - 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

1. DFS - Depth - First - Search - 깊이 우선 탐색

그래프를 나타내는 두 가지 방식

• 인접 행렬: 2차원 배열로 그래프의 연결관계를 표현하는 방식
• 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식

인접 행렬

인접 행렬 초기화

다음 이차원 배열을 통해 1번과 0번 노드의 간선의 가중치가 7임을 알 수 있다. 

 

인접 리스트는 '연결 리스트'라는 자료구조를 이용해 구현하는데 파이썬에서는 리스트가 append() 메소드를 제공하므로 리스트가 배열과 연결 리스트의 기능을 모두 기본으로 제공한다.

인접 행렬은 속도는 빠르지만 메모리 효율이 낮고, 인접 리스트는 속도는 느리지만 메모리 효율이 높다.

 

DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택 최상단 노드를 꺼낸다. 

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

다음과 같은 그래프를 DFS로 탐색하는 코드를 보자

 

2. BFS - Breadth-First-Search - 너비 우선 탐색

쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 가장 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데, BFS는 그 반대다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 거내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

위의 그래프를 BFS로 탐색하는 코드를 보자

 

 

정리

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

1-1. DFS 문제

음료수 얼려먹기

NxM 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

def dfs(x, y):
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
if array[x][y] == 0:
array[x][y] = 1
dfs(x-1, y)
dfs(x+1, y)
dfs(x, y+1)
dfs(x, y-1)
return True
return False

 

dfs 함수에서 매개 변수를 x, y 좌표로 받아서, 후에 이중 반복문을 통해 모든 좌표에서 확인이 가능하도록 구현한 것이 인상적이었다. DFS는 재귀함수를 통해 구현하므로 본 문제에서도 해당 좌표의 상, 하, 좌, 우의 칸에 대한 처리를 재귀함수를 통해 수행한다. 재귀함수들이 인접한 칸의 값들을 미리 다 1로 바꾸어주기 때문에 dfs()가 처음 호출된 좌표에서만 True 값이 나올 수 있는 것이다. 

 

2-1. BFS 문제

미로 찾기

NxM 형태의 미로가 있다. 시작 위치는 (1, 1)이고 미로의 출구는 (N, M)에 위치하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로 없는 부분은 1로 표시된다.  시작과 마지막 칸을 모두 포함하여 미로를 탈출하기 위한 최소 이동 칸 수 를 구하시오.

백준 - 바이러스

 

백준 - 적록색맹

처음에 19행의 table[nx][ny] = True 코드를 12행 밑에 두어, 큐에서 좌표를 뽑아낸 직후 테이블에서 해당 좌표를 방문처리 하는 식으로 코드를 작성했다.  

백준 - 나이트의 이동

 

q = deque() 큐 선언을 bfs 함수 밖에 정의했더니 인덱스 에러가 났다. 큐를 매번 재정의 할 필요가 있는 것 같다. 또한 처음에는 bfs 함수로 맵 전체 좌표에 대한 최소 이동 거리를 구한 이후에 도착 지점의 값을 출력하는 식으로 코드를 짰는데, 이렇게 되면 불필요한 계산이 너무 많아진다. bfs가 원하는 좌표에 도달했을 때 해당 좌표의 거리를 출력하고 바로 종료하는 식으로 코드를 변형하여 시간과 메모리를 줄일 수 있다.