[알고리즘] 깊이우선탐색(Depth-First Search)과 파이썬 구현

깊이우선탐색(DFS)은 시작 정점에서 시작하여 한 분기만을 선택해가며 최대 깊이까지 탐색한 후 나머지 분기로 이동하여 더 이상 탐색할 정점이 없을 때까지 탐색을 수행하는 알고리즘입니다. 재귀 함수로 구현되며, 정점(=노드, vertex) 수와 간선(edge) 수를 합한 값(V+E)에 비례하는 시간 복잡도를 갖습니다. DFS로는 단절점(articulation points), 단절선, 사이클 찾기 등을 해결할 수 있습니다.

 

DFS를 구현하기 위해서는 그래프를 표현할 인접 리스트, 방문한 노드를 기록할 배열, 그리고 재귀 구조가 필요합니다.

 

예제1) 입력으로 무방향 그래프가 주어지면 그 연결 요소의 수를 구하는 프로그램을 작성하라. 입력의 첫 행에는 정점의 수 V와 간선의 수 E가 주어지며, 둘째 행부터 E번째 행까지는 한 간선의 양 끝점에 대한 식별자가 주어진다. (식별자는 1 이상의 자연수)

<입력>          <그림>
5 4        [1]───[2]───[5]
1 2         └───────────┘
2 5
5 1           [3]───[4]
3 4

풀이

1. 입력을 인접 리스트로 저장하고, 기록 배열을 초기화한다.

2. 리스트의 첫 번째 입력부터 DFS를 수행한다. 탐색한 정점을 배열에 기록한다. (방문한 정점은 빗금 표시함)

정점 1, 2, 5에 대하여 탐색하였으나 아직 방문하지 않은 정점이 존재하므로 한 번 더 실행한다.

이제 모든 정점을 방문하였으며, 탐색이 2회 실행되었다. 따라서 주어진 입력의 연결요소의 개수는 2이다.

 

import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def dfs(graph_list, vertex, visited):	# 그래프, 방문할 정점, 방문기록을 입력
    visited[vertex] = True		# 방문한 정점을 기록
    for i in graph_list[vertex]:	# 선택된 정점의 인접점에 대해 반복
        if not visited[i]:
            dfs(graph_list, i, visited)	# 미방문 정점에 대한 재귀 호출

v, e = map(int, input().split())	# 정점의 개수 v와 간선의 개수 e

graph = [[] for _ in range(v + 1)]
# 만약 v = 3이면, [[], [], [], []]처럼 리스트가 생성됨
# 각 정점의 번호가 1부터 시작하므로 인덱스가 0인 리스트는 사용하지 않음
for i in range(e):			# 각 정점의 인접점을 리스트에 입력
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

c = 0
visited = [False] * (v + 1)
for i in range(1, v + 1):		# 정점1부터 마지막 정점까지 반복
    if not visited[i]:		
        dfs(graph, i, visited)		# 미방문 정점에 대해 dfs 호출
        c += 1				# dfs가 끝날 때마다 카운트

print(c)