[파이썬, Python] 백준 1260: DFS와 BFS

문제

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

코드

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

n, m, v = map(int,input().split())


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


for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in graph:
    i.sort()

visited_d = [False for _ in range(n + 1)]
visit_num_d = [v]

def dfs(i):
    visited_d[i] = True
    for x in graph[i]:
        if visited_d[x] == False:
            visit_num_d.append(x)
            dfs(x)

visited_b = [False for _ in range(n + 1)]
visit_num_b = []
visit_num_b.append(v)
visited_b[v] = True

def bfs(n):
    que = deque([n])
    while que:
        n = que.popleft()
        for i in graph[n]:
            if not visited_b[i]:
                visit_num_b.append(i)
                visited_b[i] = True
                que.append(i)
dfs(v)     
bfs(v)

for i in visit_num_d:
    print(i, end=' ')
print()
for j in visit_num_b:
    print(j, end=' ')

설명

dfs의 경우 다른 문제에 자세한 풀이가 있으므로 앞에서 다루지 않았던 bfs 위주로 설명을 해보려고 한다.
https://looancheong.tistory.com/135

[파이썬, Python] 백준 24479: 알고리즘 수업 - 깊이 우선 탐색 1

bfs의 경우 deque을 사용하여 해결했다.
리스트로도 구현은 가능하지만 deque을 이용하는 방식이 시간복잡도 측면에서 더 나은 방법이기 때문에 deque을 사용한다.

que라는 deque을 하나 만들어주고, que가 존재하는 동안 popleft()를 통하여 덱의 가장 왼쪽에 있는 수를 pop 해준다.
이후 이 n과 연결되어 있는 노드들 중에 방문하지 않은 노드를 찾고 방문하여 탐색을 해준다.
즉 방문하지 않은 노드만 탐색을 해주면 된다.

dfs와의 차이점은 dfs는 한 트리의 끝부분까지 탐색을 진행하고 다음 갈림길로 넘어간다면,
bfs는 인접 노드를 우선 탐색하며 트리를 차례대로 내려간다.