[Baekjoon/Python] 1260번: DFS와 BFS - 효과는 굉장했다!

[Baekjoon/Python] 1260번: DFS와 BFS - 효과는 굉장했다!

반응형

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

알고리즘 분류

그래프 이론

그래프 탐색

너비 우선 탐색

깊이 우선 탐색

SOLUTION

import sys from collections import deque def dfs(graph, start_node): queue = deque([start_node]) visit = [] while queue: node = queue.pop() # 가장 깊숙이 있는 노드부터 탐색해야 하므로 if node not in visit: # 이미 방문한 노드면 지나감 visit.append(node) if node not in graph: return visit queue.extend(graph[node]) return visit def bfs(graph, start_node): queue = deque([start_node]) visit = [] while queue: node = queue.popleft() # 순차적으로 탐색해야 하므로 if node not in visit: # 이미 방문한 노드면 지나감 visit.append(node) if node not in graph: return visit queue.extend(graph[node]) return visit N, M, V = map(int, sys.stdin.readline().split()) graph = {} for _ in range(M): key, value = map(int, sys.stdin.readline().split()) if key not in graph: graph[key] = [] if value not in graph: graph[value] = [] graph[key].append(value) graph[value].append(key) for key in graph: # 가장 깊숙이 있는 것 부터 탐색해야하므로 내림차순으로 정렬 graph[key].sort(reverse=True) print(*dfs(graph, V)) for key in graph: # 순차적으로 탐색해야하므로 오름차순으로 정렬 graph[key].sort() print(*bfs(graph, V))

from http://thflgg133.tistory.com/118 by ccl(A) rewrite - 2021-11-18 21:01:10