1260. DFS와 BFS
- DFS(Depth First Search, 깊이 우선 탐색), BFS(Breadth First Search, 너비 우선 탐색)으로 구현
- Stack과 Queue를 사용하고 방문처리를 통해 탐색
import sys
from collections import deque
input = sys.stdin.readline
n, m, v = map(int, input().split())
arr = [[] for i in range(n + 1)]
visited = [False for _ in range(n + 1)]
deq = deque()
for i in range(m):
a, b = map(int, input().split())
arr[a].append(b)
arr[b].append(a)
def dfs(start, visited):
visited[start] = True
print(start, end=' ')
for i in sorted(arr[start]):
if not visited[i]:
visited[i] = True
dfs(i, visited)
def bfs(start, visited):
visited[start] = True
print(start, end=' ')
deq.append(start)
while deq:
x = deq.popleft()
for i in sorted(arr[x]):
if not visited[i]:
print(i, end=' ')
visited[i] = True
deq.append(i)
dfs(v, visited)
visited = [False for _ in range(n + 1)]
print()
bfs(v, visited)
