오늘은 백준 1012번을 풀다가 막혀서 dfs에 대해서 더 공부해보려고 글을 씁니다.
DFS란?
DFS는 깊이 우선 탐색 알고리즘입니다.
즉 한 노드를 탐색하면 그 노드와 연결된 노드 중 방문하지 않은 곳이 없을 때까지 타고타고 들어가며 탐색하는 알고리즘입니다.
스택으로 구현될 수 있는 알고리즘이기도 합니다.
위의 그림을 스택을 이용해 설명하면 이렇습니다.
-
1을 방문처리한 후 스택에 넣습니다
-
1과 연결된 2를 방문처리하고 스택에 넣습니다.
-
2와 연결된 3을 방문처리하고 스택에 넣습니다.
-
3과 연결된 노드가 없으므로 3을 스택에서 꺼냅니다.
-
2와 연결된 노드 또한 없으므로 2를 스택에서 꺼냅니다.
-
1과 연결된 노드 4를 스택에 넣습니다.
-
반복
이렇게 스택의 구조를 이용해서 구현할 수 있습니다.
다시 말해 DFS는 한 길로 쭉 파고 들어가는 알고리즘이라고 할 수 있습니다.
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)
graph = [
[],
[2, 3],
[1, 4],
[1, 3, 4],
[2, 4]
]
visited = [False] * 5
dfs(graph, 1, visited)코드 설명
graph배열은 각 노드에 연결된 노드를 나타냅니다.
예를 들어 graph[1]은 노드 1에 연결된 모든 노드를 리스트 형태로 확인할 수 있습니다.
visited 배열은 각 노드가 방문되었는지 저장합니다.
dfs함수는 graph, v(현재노드), visited를 인자로 받습니다.
visited[v] = True
print(v,end=' ')먼저 v에 방문처리를 해줍니다. 방문했으므로 출력도 해줍니다.
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)자신과 연결된 모든 노드를 확인하기 위해서 graph[v]로 반복문을 실행합니다.
각 노드들이 방문되었는지 확인하고, 방문하지 않은 노드인 경우에만 dfs를 호출합니다.
장점
재귀함수를 이용하였기 때문에 스택을 사용할 필요가 없습니다.
또한 이해가 아주 쉽습니다.
단점
제가 부딪힌 한계이기도 한데, 파이썬에는 최대 재귀한도 깊이 에러(RecursionError: maximum recursion depth exceeded in comparison)가 존재합니다. 이는 재귀함수가 또 다른 재귀함수를 부르는 과정이 1000번 이상 반복되면 발생하는 오류입니다.
파이썬의 최대 재귀 한도는 1000입니다.
만약 1001개의 노드가 한 줄로 연결 되어있다면 오류가 발생하게 됩니다.
이 문제를 해결하는 방법은
1. 한도를 늘려주기
2. 반복문을 사용하기
입니다.
저는 반복문과 스택을 이용해 dfs함수를 다시 만들어보겠습니다.
반복문 이용한 구현
코드
def dfs(graph, v, visited):
stack = [v]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
print(v, end=' ')
for node in graph[v]:
if not visited[node]:
stack.append(node)
graph = [
[],
[2, 3],
[1, 4],
[1, 4],
[2, 3]
]
visited = [False] * 5
dfs(graph, 1, visited)코드 설명
스택에 첫 노드를 추가합니다(초기화)
- 스택에서 노드를 하나 빼냅니다.
- 그 노드가 방문된 것인지 확인하고 아니라면 방문표시를 합니다.
- 그 노드와 연결된 노드 중 방문하지 않은 노드를 모두 스택에 넣습니다.
- 스택이 모두 빌 때까지 반복합니다.
오늘은 dfs에 대해서 두 가지 방법으로 코드를 작성하고 정리해보았습니다.
아직 백준1012번을 풀지 못했지만... 풀게 되면 올리도록 하겠습니다!
끝.
