1260번 - DFS와 BFS

시간제한 : 2초
메모리 제한 : 128MB

---

문제

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

---

입력

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

---

출력

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

---

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

---

예제 출력 1

1 2 4 3
1 2 3 4

---

코드

import sys
from collections import deque
sys.setrecursionlimit(10000)


N, M, V = map(int, sys.stdin.readline().strip().split())

# 관계 그래프 생성
graph = [[] for _ in range(N+1)]

for _ in range(M):
  a, b = map(int, sys.stdin.readline().strip().split())
  graph[a].append(b)
  graph[b].append(a)

# 정점 번호가 작은 것을 먼저 방문하기 위해 그래프 정렬
for i in range(1, N+1):
  graph[i].sort()

# DFS
ch = [0] * (N+1)

DFS_answer = []

def DFS(v, ch, graph):
  ch[v] = 1
  DFS_answer.append(v)
  for nv in graph[v]:
    if ch[nv] == 0:
      DFS(nv, ch, graph)

DFS(V, ch, graph)

# BFS
ch = [0] * (N+1)

Q = deque()
Q.append(V)
BFS_answer = []
BFS_answer.append(V)
ch[V] = 1

while Q:
  n = len(Q)
  for i in range(n):
    v = Q.popleft()
    for nv in graph[v]:
      if ch[nv] == 0:
        BFS_answer.append(nv)
        ch[nv] = 1
        Q.append(nv)

print(*DFS_answer)
print(*BFS_answer)

---

풀이

시간 : 76ms
메모리 : 34192KB

이 문제는 그래프와 DFS, BFS 세 가지를 다 알아야 풀이가 가능한 문제이다.

먼저 N, M, V를 입력받고 M개의 관계를 입력받아 관계 그래프를 생성하면 된다.
이때 나는 인접리스트로 생성했으며, 문제에 양방향이라 명시되어 있으므로 무방향 그래프로 만들었다.
또한, 정점 번호가 작은 것부터 먼저 방문해야하므로 각각의 정점의 리스트마다 정렬을 했다.

그 후 해당 정점에 방문했는지 확인하는 ch 리스트를 DFS와 BFS 각각 따로 초기화해 생성한다.

DFS

• 먼저 DFS를 가장 먼저 방문할 정점인 V를 기준으로 호출한다.
• 호출하면 먼저 호출된 정점을 ch에 표시한 후 결과로 출력할 DFS_answer에 추가된다.
• 그 후 for문을 이용해 v와 연결된 정점들 중 이미 방문하지 않은 정점 즉, ch[nv] == 0인 정점들을 기준으로 재귀적 호출을 해준다.
• 이렇게 모든 호출이 끝나면 연결된 모든 정점들을 DFS 알고리즘을 이용해 방문했으므로 종료된다.

BFS

• 먼저 가장 먼저 방문할 V 정점을 Q에 넣고 ch에 표시한 후 결과로 출력할 BFS_answer에 추가해준다.
• 그 후 V와 연결된 정점들을 작은 순으로 BFS_answer에 추가해주며 Q에 삽입한다.
• 이때, 그냥 추가하거나 삽입하는 것이 아닌 이미 추가되지 않은 정점인 경우 즉, ch[nv] == 0인 경우에만 실행한다.
• 이렇게 다 호출된 후엔 연결된 모든 정점들을 BFS 알고리즘을 이용해 방문했으므로 종료된다.

DFS와 BFS 알고리즘을 이용해 탐색이 끝나면 출력할 DFS_answer와 BFS_answer를 * 문자를 이용해 []와 ,를 생략하고 출력해준다.