[Python | 백준 1260번] DFS와 BFS

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

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

---

내 풀이

dfs(깊이 우선 탐색)와 bfs(너비 우선탐색)에 대한 기초 문제 이다. 두 방식을 모두 고려하여 문제를 풀어야 한다. 

 

dfs는 보통 stack을 활용한 방식으로 풀고bfs는 보통 queue를 활용하여 푼다. queue를 활용하기 위해서는 collections 모듈에서 deque 클래스를 불러와야한다. 

deque없이 그냥 리스트 pop 처리 해도 되긴하는데 보통은 시간초과 문제에 당면하기 때문에

풀면서 익숙해지도록 쓰는 연습을 하는 것이 좋다.

 

# 34060kb 704ms

from collections import deque

max_num, lines, start = map(int, input().split())
relations = [[] for _ in range(max_num)]

# 관계 정리 및 정렬
for _ in range(lines):
  a, b = map(int, input().split())
  relations[a-1].append(b)
  relations[b-1].append(a)

for rel in relations:
  rel.sort()

# dfs
def dfs(st):
  stack = [st]
  visited = []

  while stack:
    v = stack.pop()
    if v not in visited:
      visited.append(v)
      stack.extend(reversed(relations[v-1]))
  print(*visited)

# bfs
def bfs(st):
  queue = [st]
  visited = []

  while queue:
    v = queue.pop(0)
    if v not in visited:
      visited.append(v)
      queue.extend(relations[v-1])
  print(*visited)

dfs(start)
bfs(start)

 

메모

dfs, bfs