문제 풀이
- DFS의 경우 재귀 함수를 이용하여 그래프를 탐색한다.
- BFS의 경우 queue를 이용하여 그래프를 탐색한다.
# BOJ1260_DFS와BFS
from collections import deque
n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
for i in range(len(graph)):
graph[i].sort()
def dfs(graph, start):
global dfs_answer, visited
visited[start] = True
dfs_answer.append(start)
for i in graph[start]:
if not visited[i]:
dfs(graph, i)
visited[i] = True
def bfs(graph, start):
global bfs_answer, visited
visited[start] = True
queue = deque([start])
while(queue):
x = queue.popleft()
bfs_answer.append(x)
for i in graph[x]:
if not visited[i]:
queue.append(i)
visited[i] = True
dfs_answer = []
bfs_answer = []
dfs(graph, v)
visited = [False for _ in range(n+1)]
bfs(graph, v)
for elem in dfs_answer:
print(elem, end=' ')
print()
for elem in bfs_answer:
print(elem, end=' ')
'''
dfs - 재귀를 이용하여 그래프를 탐색
bfs - 큐를 이용하여 그래프를 탐색
'''
'Algorithm study' 카테고리의 다른 글
[백준 1197 / Python(파이썬)] 최소 스패닝 트리 (0) | 2022.07.29 |
---|---|
[백준 1700 / 파이썬(Python)] 멀티탭 스케줄링 (0) | 2022.07.28 |
[백준 14179/파이썬(Python)] 빗물 (0) | 2022.07.18 |
CH 06. 스택(Stack) (0) | 2022.03.24 |
Ch 05. 큐(Queue) (0) | 2022.03.24 |