[알고리즘]백준 1260 : DFS와 BFS (파이썬)

1260번: DFS와 BFS

그래프의 탐색 방법인 DFS와 BFS에 대해 묻는 문제이다.

처음에는 dictionary에 주어진 간선만 넣었는데 잘못 생각했었다.
2→5 간선이 주어진다고 하면 graph[2] = 5 뿐 아니라 graph[5] = 2 5→2에 대한 간선도 포함되어 있는 것이다. 이 정보를 모두 dictionary 형태의 graph에 삽입해야 온전한 탐색이 이루어질 수 있다.

코드를 제출했는데 고려하지 못한 케이스가 있었다. 시작 노드에서 갈 수 있는 노드가 없는 경우이다.

start = 5, graph = {1 : [2, 3]}

위와 같은 경우이다. 이 경우 단순한 dictionary를 사용하면 해당 key가 없는 경우 keyError를 반환한다. 이를 방지하기 위해 collections 모듈의 defaultdict 를 사용하여 key가 없는 경우에 Error를 반환하지 않도록 했다.

import sys
from collections import deque, defaultdict

input = sys.stdin.readline

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

graph = defaultdict(list)
for _ in range(m):
    s, e = map(int, input().split())
    graph[s] = graph.get(s, []) + [e]
    graph[e] = graph.get(e, []) + [s]

# print(graph)
visited = []

def dfs(cur_v):
    visited.append(cur_v)
    for v in sorted(graph[cur_v]):
        if v not in visited:
            dfs(v)
    return visited
            
def bfs(start_v):
    visited = [start_v]
    queue = deque([start_v])
    while queue:
        cur_v = queue.popleft()
        for v in sorted(graph[cur_v]):
            if v not in visited:
                visited.append(v)
                queue.append(v)
    return visited

print(*dfs(v))
print(*bfs(v))