[백준] 1260. DFS와 BFS - 파이썬

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

1260번: DFS와 BFS

 

풀이

기본적인 DFS, BFS 구현 문제.

dictionary를 사용한다면, 없는 key에 접근하지 않도록 유의할 것.

예외처리를 하지 않고 제출했다가, 런타임 에러(keyError)가 남.

line 30~32, 49~51과 같이 정점에 연결된 간선이 없을 때를 예외처리 해 주면 된다.

아마 정점이 딱 하나만 들어왔을 때 Error가 났을 듯.

 

from collections import deque
N, M, V = map(int, input().split())

graph = dict()

# 그래프 저장 (간선 입력)
for _ in range(M):
    a, b = map(int, input().split())

    if graph.get(a, -1) == -1:
        graph[a] = [b]
    else:
        graph[a].append(b)

    if graph.get(b, -1) == -1:
        graph[b] = [a]
    else:
        graph[b].append(a)

stack = deque([V])
visited = []

# DFS
while stack:
    v = stack.pop()

    if v in visited:
        continue
    else:
        if graph.get(v, -1) == -1:
            visited.append(v)
            continue
        stack.extend(sorted(graph[v], key=lambda x: -x))
        visited.append(v)

print(*visited)

# BFS

queue = deque([V])
visited = []

while queue:
    v = queue.popleft()

    if v in visited:
        continue
    else:
        if graph.get(v, -1) == -1:
            visited.append(v)
            continue
        queue.extend(sorted(graph[v], key=lambda x: x))
        visited.append(v)

print(*visited)