[Algorithm] DFS

이번에는 탐색 알고리즘 DFS에 대하여 공부해 보았습니다. DFS와 BFS를 공부하기 전에 스택과 큐, 재귀 함수에 대한 간단한 개념 정도는 알고 있는 것이 좋다. 그렇다면 DFS란 무엇일까? DFS란 Depth-First Search의 줄임말로 깊이 우선 탐색 즉, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다. 그래프 표현방식에는 크게 2가지로 인접 행렬(Adjacency Matrix)와 인접 리스트(Adjacency List)가 있다.

 

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

 

그래프

위의 그래프를 예시로 인접 행렬 방식과 인접 리스트 방식으로 나타내 보겠습니다.

 

	0	1	2
0	0	7	5
1	7	0	무한
2	5	무한	0

인접 행렬 방식

 

연결이 되어있지 않은 노드끼리는 무한의 비용이라고 작성합니다. 현재 0은 인접한 노드가 1과 2 두 개이므로 인접 행렬로 나타내면 0, 7, 5가 되고 1의 경우에는 인접한 노드가 0 밖에 없으므로 7, 0, 무한이 됩니다. 마찬가지로 2도 인접한 노드가 0밖에 없으므로 5, 무한, 0이 됩니다. 그렇다면 인접 리스트 방식은 어떨까요?

 

인접 리스트 방식

 

인접 리스트 방식에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장합니다. 인접 행렬 방식은 모든 관계를 저장하지만 인접 리스트 방식은 연결된 정보만을 저장합니다.

 

그렇다면 이제 DFS를 구현해 보겠습니다. DFS는 스택을 이용하는 알고리즘이므로 재귀 함수를 이용하여 구현할 수도 있습니다. 아래의 그래프를 예시로 작성하겠습니다.

위 그래프의 각 노드가 연결된 정보를 구해보겠습니다. 각 노드가 연결된 정보를 구하는 방법은 해당 노드의 인접한 노드의 값을 구해주면 됩니다. 숫자 1에 대한 노드의 인접한 노드를 보면 연결된 노드가 총 3가지로 2와 3 그리고 8이 연결되있음을 알 수 있습니다. 다른수도 마찬가지 방법으로 구하면 아래의 표가 완성됩니다.

1	2, 3, 8
2	1, 3
3	1, 4, 5
4	3, 5
5	3, 4
6	7
7	2, 6, 8
8	1, 7

각 노드가 연결된 정보

 

def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
	
    # 각 노드와 연결된 정보를 순회하면서
    for i in graph[v]:
    	# 해당 노드를 방문하지 않았다면 탐색
    	if not visited[i]:
        	dfs(graph, i, visted)
      
#  노드와 연결된 정보
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

#  각 노드를 한 번씩만 방문하기 위한 visited 리스트
visited = [False] * 9
  
dfs(graph, 1, visited)

'''
출력
1 2 7 6 8 3 4 5
'''