https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
풀이
기본적인 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)