[백준 1260 / 파이썬 풀이] DFS와 BFS

from collections import deque

def dfs(v):
    print(v, end=' ')
    visited[v] = 1
    for i in graph[v]:
        if visited[i] != 1:
            dfs(i)

def bfs(v):
    visited[v] = 0
    q = deque()
    q.append(v)

    while q:
        c = q.popleft()
        print(c, end=' ')
        for j in graph[c]:
            if visited[j]:
                q.append(j)
                visited[j] = 0

N, M, V = map(int, input().split())

graph = [[] for _ in range(N+1)]

visited = [0] * (N+1)


for i in range(M):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

for i in graph:
    i.sort()

dfs(V)
print()
bfs(V)

각 노드에 대한 그래프를 먼저 그린 후 방문배열을 통해 dfs와 bfs를 구해준다.

 

주의해야 할 부분은

방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문

문구를 주의해야 한다. 각 노드별로 가장 정점 번호가 작은 것을 방문해야 하기 때문에 각 그래프를 sort 해줌으로서 가장 작은 노드부터 방문 할 수 있게 해준다.

또한, dfs 후 bfs를 순회하게 되는데 이 때 방문 리스트가 0 -> 1 이 되어 있으므로 다시 1 -> 0 으로 바꿔줘야 한다.