[백준 - DFS,BFS] 1260 - DFS와 BFS - 파이썬
by Dojin Kim
1260 - DFS와 BFS [DFS, BFS]
출처 : 백준 1260 DFS와 BFS
문제
Graph 노드들과 엣지들이 주어지고, 시작 노드가 주어진다. 해당 정보들로 DFS와 BFS로 각각 순회해서 방문한 순을 출력하는 것이 문제의 목표이다. DFS, BFS 문제의 가장 기본이 되는 문제이다. 양방향 그래프이기 때문에 엣지의 정보가 주어지면 반대로도 이어줘야 한다. 예를 들어, 2 4가 주어졌다면 2 -> 4 뿐만 아니라 4 -> 2라는 엣지 정보도 추가해줘야 하는 것이다. 그러고 나서 여러 갈래로 갈 수 있을 때 작은 수부터 순회하기 때문에 엣지들을 정렬 시켜줘야 한다.
DFS는 주로 visited라는 방문여부에 대한 배열을 사용해서 재귀 구조로 구현을 한다. 방문헀다면 자신을 호출하지 않고, 방문하지 않은 노드이면 재귀로 방문을 한다.
BFS는 queue를 사용해서 순회를 한다. 주어진 노드와 연결된 모든 노드중 방문하지 않는 노드들을 순회하고 해당 노드들을 다시 queue 삽입한다.
***주의해야할 점
Python에서 list를 queue처럼 사용할 수 있다. pop(0)를 하면 index 0 에 있는 숫자가 pop된다, 하지만, 이 방법은 O(n)의 시간복잡도로 pop하기 때문에 매우 느리다. 그래서 이 문제에서는 시간초과를 막기 위해 collections의 deque를 사용해야 한다. 해당 자료구조는 O(1)의 시간복잡도로 pop하도록 구현 되어있다.
풀이
# BOJ 1260 - DFS와 BFS
import sys
from collections import deque
r = sys.stdin.readline
def dfs(ans, v, g):
for ele in g[v]:
if ele not in ans:
ans.append(ele)
dfs(ans, ele, g)
return ans
def bfs(ans, q, g):
while q:
x = q.popleft()
ans.append(x)
for ele in g[x]:
if ele not in ans and ele not in q:
q.append(ele)
return ans
N, M, V = map(int, r().split())
graph = dict()
que = deque()
for i in range(1, N+1):
graph[i] = []
# edge들 추가
for i in range(M):
edge = list(map(int, r().split()))
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
# 정렬 및 que에 값 추가
for j in graph.keys():
graph[j] = sorted(graph[j])
if j == V:
que.extend(graph[j])
print(" ".join(map(str, dfs([V], V, graph))))
print(" ".join(map(str, bfs([V], que, graph))))
Subscribe via RSS
