백준 1260 DFS와 BFS - python

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

visited_dfs = [False]*(N+1)
def dfs(graph, V, visited_dfs):
    visited_dfs[V] = True
    print(V, end=' ')
    for i in sorted(graph[V]):
        if not visited_dfs[i]:
            dfs(graph, i, visited_dfs)
dfs(graph, V, visited_dfs)
print()
from collections import deque

visited_bfs = [False]*(N+1)
def bfs(graph, V, visited_bfs):
    queue = deque([V])
    visited_bfs[V] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in sorted(graph[v]):
            if not visited_bfs[i]:
                queue.append(i)
                visited_bfs[i] = True
bfs(graph, V, visited_bfs)

동빈나님의 youtube 강의를 보고 공부했습니다. (https://www.youtube.com/watch?v=7C9RgOcvkvo&t=2401s)

기준이 되는 정점을 index로 갖고 간선으로 연결된 상대 정점을 요소로 갖는 2차원 list를 만들었습니다. (graph = [[2], [2], [0, 1]] 이면 1번 정점(index = 1)은 graph[1]의 요소인 2번 정점과 연결되어 있는 것임)

그리고 DFS는 재귀를 이용했고, BFS는 queue를 이용했습니다.