DFS / BFS 기초 구현
DFS
# n = 노드의 수, m = 엣지의 수, v = 시작 노드
n, m, v = map(int, input().split())
# 인접 행렬 초기화: (n+1) x (n+1) 크기의 0으로 채워진 행렬 생성
# 인접 행렬은 그래프의 연결 관계를 표현하는 데 사용
gp = [[0] * (n + 1) for _ in range(n + 1)]
# 엣지 정보를 입력받아 인접 행렬을 업데이트
for _ in range(m):
a, b = map(int, input().split())
# 무방향 그래프이므로 두 노드 a와 b를 서로 연결
gp[a][b] = gp[b][a] = 1 # a와 b가 연결되어 있음을 표시
# DFS 방문 리스트 초기화: 각 노드의 방문 여부를 저장
vis_dfs = [0] * (n + 1) # DFS용 방문 리스트
vis_bfs = [0] * (n + 1) # BFS용 방문 리스트
def dfs(v):
vis_dfs[v] = 1 # 현재 노드 v를 방문 처리
print(v, end=' ') # 방문한 노드 출력
# 현재 노드 v와 연결된 노드를 탐색
for i in range(1, n + 1):
# 연결되어 있고 아직 방문하지 않은 노드에 대해 DFS 재귀 호출
if gp[v][i] == 1 and vis_dfs[i] == 0:
dfs(i) # 재귀적으로 DFS 호출BFS
from collections import deque
def bfs(v):
queue = deque([v]) # 시작 노드 v를 큐에 추가
vis_bfs[v] = 1 # 시작 노드 v를 방문 처리
while queue: # 큐가 빌 때까지 반복
v = queue.popleft() # 큐에서 노드 v를 꺼냄
print(v, end=' ') # 방문한 노드 출력
# 현재 노드 v와 연결된 노드를 탐색
for i in range(1, n + 1):
# 연결되어 있고 아직 방문하지 않은 노드에 대해 큐에 추가
if gp[v][i] == 1 and vis_bfs[i] == 0:
queue.append(i) # 노드 i를 큐에 추가
vis_bfs[i] = 1 # 노드 i를 방문 처리
# DFS 호출
print("DFS:", end=' ')
dfs(v) # 시작 노드 v로 DFS 수행
# 줄 바꿈
print()
# BFS 호출
print("BFS:", end=' ')
bfs(v) # 시작 노드 v로 BFS 수행
