## 의사코드 ##
# DFS -> 재귀
# # 해당 노드 방문 처리
# visited[node] = True
# # 탐색 순서 출력
# print(node, end = ' ')
# # 탐색
# for i in graph[node]:
# if not visited[i]:
# dfs(graph, i, visited)
# BFS -> deque
# # 큐에 시작 정점 삽입
# q = deque[v]
# # 시작 정점 방문 처리
# visited[v] = True
# # 탐색 순서 출력
# print(node, end = ' ')
# # 탐색
# while q:
# node = q.popleft()
# for i in graph[node]:
# if not visited[i]:
# visited[i] = True
# q.append(i)
첫 번째 시도
import sys
input = sys.stdin.readline
from collections import deque
# 정점의 개수(n), 간선의 개수(m), 시작 정점(v)
n, m, v = map(int, input().split())
# 그래프에 값 입력
graph = [[] for _ in range(n+1)]
for _ in range(1, m+1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a) # 주어진 간선은 양방향
# 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기 위해 오름차순 정렬
graph.sort()
# DFS 함수
def dfs(graph, node, visited):
print(node, end=' ')
visited[node] = True
for i in graph[node]:
if not visited[i]:
dfs(graph, i, visited)
# BFS 함수
def bfs(graph, start, visited):
q = deque([start])
visited[start] = True
while q:
node = q.popleft()
for i in graph[node]:
if not visited[i]:
visited[i] = True
print(i, end=' ')
q.append(i)
# visited 초기화
visited = [False] * (n+1)
# DFS 수행
dfs(graph, v, visited) # v = 시작 정점
print()
# visited 초기화
visited = [False] * (n+1)
# BFS 수행
bfs(graph, v, visited) # v = 시작 정점
-> 틀림
출력 확인
n = 4
m = 5
v = 1
graph = [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3], []]
"""
1
"""
-> dfs(), bfs() 둘 다 출력값 틀림
두 번째 시도
import sys
input = sys.stdin.readline
from collections import deque
# 정점의 개수(n), 간선의 개수(m), 시작 정점(v)
n, m, v = map(int, input().split())
# 그래프에 값 입력
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a) # 주어진 간선은 양방향
# 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기 위해 오름차순 정렬
for adj in graph:
adj.sort()
# DFS 함수
def dfs(node):
print(node, end=' ')
visited[node] = True
for i in graph[node]:
if not visited[i]:
dfs(i)
# BFS 함수
def bfs(start):
q = deque([start])
visited[start] = True
while q:
node = q.popleft()
for i in graph[node]:
if not visited[i]:
visited[i] = True
print(i, end=' ')
q.append(i)
# visited 초기화
visited = [False] * (n+1)
# DFS 수행
dfs(v) # v = 시작 정점
print()
# visited 초기화
visited = [False] * (n+1)
# BFS 수행
bfs(v) # v = 시작 정점
import sys
input = sys.stdin.readline
from collections import deque
# 정점의 개수(n), 간선의 개수(m), 시작 정점(v)
n, m, v = map(int, input().split())
# 그래프에 값 입력
graph = [[] for _ in range(n+1)]
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a) # 주어진 간선은 양방향
# 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하기 위해 오름차순 정렬
for adj in graph:
adj.sort()
# DFS 함수
def dfs(node):
print(node, end=' ')
visited[node] = True
for i in graph[node]:
if not visited[i]:
dfs(i)
# BFS 함수
def bfs(start):
q = deque([start])
while q:
node = q.popleft()
# 시작 정점부터 출력하기 위해 시작 정점의 방문처리를 여기서 진행
if not visited[node]:
visited[node] = True
print(node, end=' ')
for i in graph[node]:
if not visited[i]:
q.append(i)
# visited 초기화
visited = [False] * (n+1)
# DFS 수행
dfs(v) # v = 시작 정점
print()
# visited 초기화
visited = [False] * (n+1)
# BFS 수행
bfs(v) # v = 시작 정점
