깊이 우선 탐색 (DFS, Depth-First Search)은 그래프를 탐색하는 알고리즘 중 하나로, 이전에 탐색한 노드의 자식 노드들을 먼저 탐색하는 방식입니다. 이번 블로그 포스트에서는 DFS의 구현과 활용에 대해 알아보겠습니다.
DFS 구현
DFS를 구현하기 위해서는 스택 또는 재귀 함수를 사용할 수 있습니다. 여기서는 재귀 함수를 이용한 구현 방법을 살펴보겠습니다.
def dfs(graph, start_node, visited):
visited[start_node] = True
print(start_node, end=' ')
for neighbor in graph[start_node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited)
위 코드는 주어진 그래프와 시작 노드를 기반으로 DFS를 수행하는 함수입니다. graph는 그래프의 정보를 담은 인접 리스트 형태의 자료구조이고, start_node는 시작 노드의 인덱스를 의미합니다. visited는 방문한 노드를 표시하는 배열로, 초기값은 모두 False로 설정되어 있습니다.
DFS 함수에서는 현재 노드를 방문했음을 표시하고, 해당 노드를 출력합니다. 그리고 현재 노드와 인접한 노드들을 순회하면서 방문하지 않은 노드를 재귀적으로 탐색합니다.
DFS 활용
DFS는 그래프 탐색 외에도 다양한 문제에 활용될 수 있습니다. 여기서는 DFS를 사용한 두 가지 예시를 살펴보겠습니다.
1. 사이클 검사
DFS는 사이클의 존재 여부를 검사하는데 활용될 수 있습니다. 아래 코드는 방향 그래프에서 사이클을 검사하는 함수입니다.
def has_cycle(graph, node, visited, stack):
visited[node] = True
stack[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if has_cycle(graph, neighbor, visited, stack):
return True
elif stack[neighbor]:
return True
stack[node] = False
return False
함수는 시작 노드에서부터 DFS를 수행하며, 방문한 노드를 표시하고 스택에 넣습니다. 그리고 현재 노드와 인접한 노드들을 순회하면서 방문하지 않은 노드를 재귀적으로 탐색합니다. 만약 이미 방문한 노드가 스택에 있으면 사이클이 존재하므로 True를 반환합니다. DFS가 끝난 노드는 스택에서 제거합니다.
2. 미로 찾기
DFS는 미로 찾기 문제와 같이 경로를 찾는 문제에도 활용할 수 있습니다. 아래 코드는 2차원 배열로 표현된 미로에서 출발점부터 도착점까지의 최단 경로를 찾는 함수입니다.
def find_path(maze, start, end):
row, col = len(maze), len(maze[0])
visited = [[False] * col for _ in range(row)]
def dfs(x, y, path):
if x == end[0] and y == end[1]:
print(path)
return
visited[x][y] = True
if x > 0 and not visited[x - 1][y] and maze[x - 1][y] != 1:
dfs(x - 1, y, path + 'U')
if x < row - 1 and not visited[x + 1][y] and maze[x + 1][y] != 1:
dfs(x + 1, y, path + 'D')
if y > 0 and not visited[x][y - 1] and maze[x][y - 1] != 1:
dfs(x, y - 1, path + 'L')
if y < col - 1 and not visited[x][y + 1] and maze[x][y + 1] != 1:
dfs(x, y + 1, path + 'R')
visited[x][y] = False
dfs(start[0], start[1], "")
함수는 시작 위치에서부터 DFS를 수행하며, 방문한 위치를 표시합니다. 현재 위치에 따라 상하좌우로 이동하면서 도착점에 도달하면 경로를 출력합니다. DFS가 끝난 위치는 다시 방문할 수 있도록 방문 표시를 해제합니다.
마무리
깊이 우선 탐색은 그래프와 미로 찾기 등 다양한 문제에 유용하게 활용될 수 있습니다. 이번 포스트에서는 DFS의 구현 방법과 사이클 검사, 미로 찾기와 같은 실제 예시에 대해 알아보았습니다. DFS를 사용하여 다양한 문제를 해결해보세요!