문제 설명
•
그래프가 주어졌을 때, DFS를 수행한 결과와 BFS를 수행한 결과를 출력하는 문제
◦
단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
예제 입력/출력
•
입력1
4 5 1
1 2
1 3
1 4
2 4
3 4
Plain Text
복사
•
출력1
1 2 4 3
1 2 3 4
Plain Text
복사
제약 조건
•
◦
N: 노드의 개수
•
◦
M: 간선의 개수
문제 풀이
•
그래프 탐색을 이용하여 문제를 해결하면 된다. -
◦
DFS 알고리즘과 BFS 알고리즘을 이용
풀이 코드
from collections import deque
def solve_dfs(node):
global adj_list, visited
# base case
if visited[node]:
return
visited[node] = True
print(node, end=' ')
# recursive case
for adj_node in adj_list[node]:
solve_dfs(adj_node)
def solve_bfs(snode):
global adj_list, visited
q = deque()
q.append(snode)
visited[snode] = True
while q:
node = q.popleft()
print(node, end=' ')
for adj_node in adj_list[node]:
if visited[adj_node]:
continue
q.append(adj_node)
visited[adj_node] = True
# input
N, M, S = map(int, input().split())
adj_list = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
adj_list[a].append(b)
adj_list[b].append(a)
for node in range(1, N + 1):
adj_list[node].sort()
# solve
visited = [False] * (N + 1)
solve_dfs(S)
print()
visited = [False] * (N + 1)
solve_bfs(S)
print()
Python
복사