[백준][DFS/BFS] 2606. 바이러스 (파이썬/Python)

import sys
input = sys.stdin.readline

n = int(input().rstrip())
m = int(input().rstrip())
graph = [[] for _ in range(n + 1)]

for i in range(m):
  node1, node2 = map(int, input().split())
  graph[node1].append(node2)
  graph[node2].append(node1)

def dfs():
  visited = []
  stack = [graph[1]]
  cnt = 0

  while stack:
    num = stack.pop()
    print(num)
    for i in num:
      if not i in visited:
        visited.append(i)
        stack.append(graph[i])
        cnt += 1
  print(cnt - 1)

dfs()

# DFS는 스택을 사용하여 구현할 수 있다. (재귀도 가능)

일반적으로 스택을 이용한 깊이 우선 탐색은 저런 순서로 흘러간다.

그러나 이번 문제에서 구현한 코드는 저런 방식을 따르면 1 -> 2 -> 3 -> 5 -> 6이어야 하는데 2 -> 5 -> 1 -> 3 -> 6의 순서로 흘러간다. 이 부분에 대해서 다시 생각하고 문제를 풀어봐야 겠다.

https://youtu.be/_hxFgg7TLZQ

이 영상을 보면 알 수 있다.