[백준] 1260번 DFS와 BFS (Python)

👩🏻‍💻

DFS랑 BFS를 확실히 이해하고 싶어서 풀었다. 항상 원리를 제대로 이해하지 않은 채 푸는 느낌이 들어서 이 문제를 풀었는데 많은 도움이 되었다. 앞으로 DFS와 BFS 중 어느 것을 쓰는 게 효율적인지 알고 쓸 것 같다. 이 문제 강추!!!

아주 간단한 예제였지만... 코린이인 나는 이해하기 힘들었다.
하지만 풀어서 뿌듯!

코드

import sys
from collections import deque
input = sys.stdin.readline

# dfs
def dfs(v):
    dfs_visit_list[v] = 1
    print(v, end=" ")
    for i in range(1, n+1):
       if dfs_visit_list[i] == 0 and graph[v][i]:
          dfs(i)

# bfs
def bfs(v):
    dq = deque()
    dq.append(v)   
    bfs_visit_list[v] = 1
    while dq:
        v = dq.popleft()
        print(v, end = " ")
        for i in range(1, n + 1):
            if bfs_visit_list[i] == 0 and graph[v][i] == 1:
                dq.append(i)
                bfs_visit_list[i] = 1
   
n, m, v = map(int, input().split())

graph = [[0] * (n + 1) for _ in range(n + 1)]
bfs_visit_list = [0] * (n + 1)
dfs_visit_list = [0] * (n + 1)

for _ in range(m):
  a, b = map(int, input().split())
  graph[a][b] = graph[b][a] = 1 # 연결해주기

dfs(v)
print()
bfs(v)