문제
접근
DFS, BFS를 구현하기만 하면 되므로 설명은 따로 하지 않겠다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque
n, m, v = map(int, input().split(' '))
adj = [[0]*(n+1) for _ in range(n+1)]
visit = [0] * (n+1)
for i in range(m):
a, b = map(int, input().split(' '))
adj[a][b] = adj[b][a] = 1
def dfs(start):
q = [start]
while q:
node = q.pop(-1)
if visit[node]:
continue
visit[node] = 1
print(node, end=' ')
for i in range(n,0, -1):
if visit[i] == 0 and adj[node][i] == 1:
q.append(i)
def bfs(start):
q = deque()
q.append(start)
visit[start] = 1
while q:
node = q.popleft()
print(node, end=' ')
for i in range(1,n+1):
if visit[i] == 0 and adj[node][i] == 1:
q.append(i)
visit[i] = 1
dfs(v)
visit = [0] * (n+1)
print()
bfs(v)