안녕하세요, 프로그래밍에 관심이 많으신 분들께 파이썬을 이용한 깊이 우선 탐색 (Depth First Search, 이하 DFS)에 대해 알려드릴 예정입니다. 그래프 탐색 알고리즘 중 하나인 DFS는 많은 분야에서 활용됩니다. 이 글에서는 기본 개념부터 실제 파이썬 코드를 통한 구현, 그리고 DFS의 활용 예시까지 알아보겠습니다.
1. 깊이 우선 탐색 (DFS)란?
DFS는 그래프의 모든 노드를 방문하는 방법 중 하나로, "깊이 우선"이라는 이름에서 알 수 있듯이 가장 깊숙히 들어갈 수 있는 노드를 우선적으로 탐색하는 방식입니다. DFS는 미로 찾기와 같은 문제에서 경로를 찾는데 사용되며, 특히 모든 노드를 방문해야 하는 경우에 유용합니다.
DFS는 다음의 단계를 거쳐 진행됩니다.
- 시작 노드를 방문하고 스택에 추가합니다.
- 현재 스택의 맨 위 노드에 연결된, 아직 방문하지 않은 노드가 있으면 그 노드를 방문하고 스택에 추가합니다. 방문한 노드가 없으면 스택에서 최상단 노드를 제거합니다.
- 스택이 비어있을 때까지 2번을 반복합니다.
2. 파이썬으로 DFS 구현하기
DFS는 재귀 함수를 이용하여 간단하게 구현할 수 있습니다. 아래는 기본적인 DFS 구현 코드입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | # DFS 함수 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보를 표현 (2차원 리스트) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * 9 # 정의된 DFS 함수 호출 dfs(graph, 1, visited) | cs |
이 코드에서 dfs 함수는 주어진 그래프에 대해 특정 노드를 시작으로 DFS를 수행합니다. 함수를 호출할 때마다 해당 노드를 방문처리하며, 해당 노드에 연결된 모든 노드들 중 아직 방문하지 않은 노드에 대해 재귀적으로 dfs 함수를 호출합니다.
3. 파이썬으로 DFS 구현하기 - 스택 활용
DFS는 재귀 함수로 구현이 가능하지만, 스택 자료구조를 이용해 구현할 수도 있습니다. 아래는 스택을 활용한 DFS 구현 코드입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | # 스택을 활용한 DFS 함수 정의 def dfs_stack(graph, start_node): visited, stack = list(), list() stack.append(start_node) while stack: node = stack.pop() if node not in visited: visited.append(node) stack.extend(graph[node]) return visited # 각 노드가 연결된 정보를 표현 (2차원 리스트) graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'G'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['E'], 'G': ['C'] } # 스택을 활용한 DFS 함수 호출 print(dfs_stack(graph, 'A')) | cs |
이 코드에서 dfs_stack 함수는 주어진 그래프에 대해 특정 노드를 시작으로 스택을 활용한 DFS를 수행합니다. 함수는 아직 방문하지 않은 노드를 방문하고 해당 노드를 스택에 추가하는 과정을 반복하며, 더이상 방문할 노드가 없을 때까지 스택에서 노드를 제거해 나갑니다.
4. DFS 활용 예제
DFS는 다양한 문제 해결에 활용될 수 있습니다. 미로 찾기, 경로 찾기 등에서 유용하게 활용됩니다. 이제 복잡한 문제를 해결하는 예제를 통해 DFS의 활용을 살펴보겠습니다.
예제 1: 미로 찾기
미로 찾기 문제는 주어진 미로에서 시작점에서 목표점까지 가는 경로를 찾는 문제입니다. 이를 DFS로 해결해보겠습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | # DFS를 이용한 미로 찾기 함수 정의 def dfs_maze(maze, start, end): stack = [(start)] directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 상하좌우 while stack: pos = stack.pop() maze[pos[0]][pos[1]] = 2 # 방문한 위치는 2로 표시 if pos == end: return True for dx, dy in directions: x, y = pos[0] + dx, pos[1] + dy if (0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0): # 아직 방문하지 않은 위치라면 stack.append((x, y)) return False # 미로 정보 (0: 이동가능, 1: 벽, 2: 방문 위치) maze = [ [0, 1, 0, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [0, 0, 0, 0, 0] ] start, end = (0, 0), (4, 4) # 미로 찾기 함수 호출 print(dfs_maze(maze, start, end)) | cs |
예제 2: 경로 찾기
DFS는 그래프 내의 두 노드 사이의 경로를 찾는데도 사용됩니다. 이를 파이썬으로 구현해보겠습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | # DFS를 이용한 경로 찾기 함수 정의 def dfs_paths(graph, start, goal): stack = [(start, [start])] while stack: (vertex, path) = stack.pop() for next in set(graph[vertex]) - set(path): if next == goal: yield path + [next] else: stack.append((next, path + [next])) # 각 노드가 연결된 정보를 표현 (2차원 리스트) graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'G'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['E'], 'G': ['C'] } # 경로 찾기 함수 호출 print(list(dfs_paths(graph, 'A', 'F'))) | cs |
여기서는 'A' 노드에서 'F' 노드로 가는 모든 경로를 찾는 예제를 보여드렸습니다.
마치며
DFS는 그래프에서 중요한 탐색 알고리즘 중 하나로, 다양한 문제에 활용될 수 있습니다. 이 글에서는 파이썬을 이용해 DFS를 간단하게 구현해보았습니다. 그래프와 DFS에 대한 기본적인 이해를 통해, 이 알고리즘을 실제 문제 해결에 활용하실 수 있기를 바랍니다. 항상 즐거운 코딩 되세요!
댓글 없음:
댓글 쓰기