Algorithm | 2. DFS

1. 준비

• stack 리스트에는 현재 node와 앞으로 탐색해야 할 node가 담겨있다. stack은 가장 나중에 담긴 것을 가장 먼저 탐색하므로 순서를 잘 생각하며 append한다.

• visited는 빈 리스트로 초기화한다. node에 방문했을 때 차례대로 append하면, 방문한 순서를 알 수 있다.

• DFS는 그래프가 인접 노드를 확인할 수 있는 그래프가 필요하다. 아래 두 가지 방식이 있는데,
  - 인접 행렬 방식
  - 인접 리스트 방식
  이 두 가지의 장단점은 깃헙에 정리두었다.
  장단점 알아가기

• 목표 : [[], [2, 3], [1, 5], [1, 4], [3, 5], [2, 4]]

  • 항상 번호와 index 사이에서 오류가 잘 나기 마련이어서 애초에 0행을 만들어주지만 사용하지 않는 것으로 방어 코딩(?)을 해보겠다.
  • input값을 받아 어떻게든 graph를 위의 형식을 출력을 한다.

  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 기능을 생각하면 순서와 상관없이 처리해주어도 되지만, 방문 순서가 다를 수 있다.

2. 반복

while stack:으로 stack이 빌 때까지 반복한다.
while문 안의 구조는 다음과 같다.

• stack에 담긴 node중에 현재 위치를 설정한다. pop()을 사용하면 가장 마지막 노드가 할당되고, 리스트에서는 삭제된다.
• 현재 노드가 방문한 노드인가?
  - 방문 처리를 한다.
  • stack에 현재 노드에 인접한 노드를 추가한다. extend()를 사용한다.
• stack이 비었을 때 visited를 리던한다.

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))

다음에는 재귀함수로 푸는 방법을 연구해봐야겠다.