from collections import deque
import sys
N, M, V = list(map(int, sys.stdin.readline().rstrip().split()))
graph = [[False] * (N + 1) for _ in range(N + 1)] #0번 인덱스는 제외하고 연결된 노드 그래프
dfs_visited = [False] * (N + 1)
bfs_visited = [False] * (N + 1)
for i in range(M): #그래프에서 연결된 부분들 True로 초기화
node1, node2 = list(map(int, sys.stdin.readline().rstrip().split()))
graph[node1][node2] = True
graph[node2][node1] = True
def dfs(node):
dfs_visited[node] = True #해당 노드 방문 완료
print(node, end=' ')
for i in range(1, N + 1): #그래프에서 해당 노드와 연결된 부분 순회
if not dfs_visited[i] and graph[node][i]: #특정 노드와 연결 되어있으면서, 그 노드를 방문하지 않ㅇ느 경우
dfs(i)
def bfs(node):
q = deque([node]) #큐에서 시작 노드는 이미 방문 완료
bfs_visited[node] = True
while q:
node = q.popleft() #먼저 방문해야하는 노드를 빼줌
print(node, end=' ')
for i in range(1, N + 1):
if not bfs_visited[i] and graph[node][i]: #방문한 노드와 연결된 노드 중, 아직 방문하지 않은 노드는 큐에 담고 방문처리함
q.append(i)
bfs_visited[i] = True
dfs(V)
print()
bfs(V)
DFS와 BFS의 기초를 학습하기에 좋은 문제였다.
기초도없는 나이기에 문제를 두 번 풀어봤다.
참고