DFS는 스택, BFS는 큐를 기반해서 작성한다.
DFS와 BFS는 모두 노드 간의 연결 상태를 파악할 수 있는 무언가가 필요한데, 나는 딕셔너리가 편하다.
출력 양식(작은 수부터 탐험하는 양식)을 맞추기 위해서는 DFS에서는 딕셔너리의 value를 reverse sort 해야했고, BFS에서는 sort해야 했다.
import sys
node_count, line_count, start_node = map(int, sys.stdin.readline().split())
graph = {}
dfs_visited = []
bfs_visited = []
dfs_stack = [start_node]
bfs_queue = [start_node]
for _ in range(line_count):
line = list(map(int, sys.stdin.readline().split()))
if line[0] in graph:
graph[line[0]].append(line[1])
else:
graph[line[0]] = [line[1]]
if line[1] in graph:
graph[line[1]].append(line[0])
else:
graph[line[1]] = [line[0]]
# dfs
if start_node not in graph: # 시작 노드가 아무것도 연결이 안되어있을수 있는 경우를 예외처리 해야한다.
print(start_node)
else:
for x in graph:
graph[x].sort(reverse=True)
while len(dfs_stack): # 더 가야할 곳이 있는 한 반복
cur = dfs_stack.pop() # 방문할 리스트중 마지막 노드를 현재 노드로 둔다.
if cur not in dfs_visited: # 현재 노드에 방문한 적 없다면
dfs_visited.append(cur) # 방문했다는 기록을 해두고
for i in graph[cur]: # 현재 노드의 인접 노드들을 하나씩 돌면서
if i not in dfs_visited: # 인접 노드에 방문한 적 없다면
dfs_stack.append(i) # 해당 노드를 방문할 리스트에 추가한다.
for x in dfs_visited:
if x == dfs_visited[-1]:
print(x)
else:
print(x, end=' ')
# bfs
if start_node not in graph: # 시작 노드가 아무것도 연결이 안되어있을수 있는 경우를 예외처리 해야한다.
print(start_node)
else:
for x in graph:
graph[x].sort()
while len(bfs_queue):
cur = bfs_queue.pop(0)
if cur not in bfs_visited:
bfs_visited.append(cur)
for i in graph[cur]:
if i not in bfs_visited:
bfs_queue.append(i)
for x in bfs_visited:
if x == bfs_visited[-1]:
print(x, end='')
else:
print(x, end=' ')