stack 리스트에는 현재 node와 앞으로 탐색해야 할 node가 담겨있다. stack은 가장 나중에 담긴 것을 가장 먼저 탐색하므로 순서를 잘 생각하며 append한다.
visited는 빈 리스트로 초기화한다. node에 방문했을 때 차례대로 append하면, 방문한 순서를 알 수 있다.
DFS는 그래프가 인접 노드를 확인할 수 있는 그래프가 필요하다. 아래 두 가지 방식이 있는데,
- 인접 행렬 방식
- 인접 리스트 방식
이 두 가지의 장단점은 깃헙에 정리두었다.
장단점 알아가기
목표 : [[], [2, 3], [1, 5], [1, 4], [3, 5], [2, 4]]
5 4
5 2
1 2
3 4
3 1
위에 처럼 input값을 받아준다면
for _ in range(M):
v1, v2 = map(int, input().split()) # 한 줄에 들어오는 것을 각각 node로 받는다.
graph[v1].append(v2) # 해당 노드의 인접 노드로 append해준다.
graph[v2].append(v1) # 무방향이므로 다른 노드에도 append해준다.
for adj in graph:
adj.sort()
처럼 graph를 만들어줄 수 있다.
sort를 해주는 이유
input이 정렬되어 들어오는 것이 아닐 수 있고, 코테 문제에 보면, 인접 노드가 여러 개일경우에는 번호가 작은 것 먼저 탐색 또는 큰 것 먼저 탐색하라는 조건이 있을 수 있기 때문이다. 따라서 일단 정렬을 해주는 것이 좋다.
DFS 기능을 생각하면 순서와 상관없이 처리해주어도 되지만, 방문 순서가 다를 수 있다.
while stack:
으로 stack이 빌 때까지 반복한다.
while문 안의 구조는 다음과 같다.
pop()
을 사용하면 가장 마지막 노드가 할당되고, 리스트에서는 삭제된다.extend()
를 사용한다.extend()를 사용하는 이유
extend() 메소드를 살펴보면, 리스트안에 리스트로 들어가는 것이 아니라, 값이 바로 들어간다. 따라서 2차원 리스트가 되는 것을 막을 수 있다.
주의해야 할 점은, stack에 넣는 것이므로, 인접한 노드가 여러 개일 경우, 어느 노드부터 탐색하라는 조건이 있을 때, 경우에 따라서reversed
를 사용해야 할 수도 있다.
아래와 같은 코드로 작성하였다. 이 코드가 내가 dfs를 이해할 수 있는 코드이다.
N, M, V = map(int, input().split()) # V부터 탐색하시오!
# 인접행렬 방식
adjacency = [[] for _ in range(N+1)]
for _ in range(M):
v1, v2 = map(int, input().split())
adjacency[v1].append(v2)
adjacency[v2].append(v1)
for adj in adjacency:
adj.sort()
def dfs(adjacency, start_node):
visited = []
stack = [start_node] # 시작
while stack: # stack이 빌 때까지
now = stack.pop()
if now not in visited: # 방문하지 않으면
visited.append(now)
stack.extend(reversed(adjacency[now])) # 작은 노드부터 탐색해야된다.
return visited
print(dfs(adjacency, V))
다음에는 재귀함수로 푸는 방법을 연구해봐야겠다.