그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입출력 설명인접 리스트로 그래프를 짜서 dfs는 stack
자료구조, bfs는 queue
자료구조를 사용했다.
n, m, v = map(int, stdin.readline().split())
graph = [[] for _ in range(n + 1)]
# 인접 리스트 방식
for i in range(m):
x, y = map(int, stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
# print(graph)
def dfs(graph, start):
visited = []
stack = [start]
while stack: # 스택이 빌 때까지
n = stack.pop()
if n not in visited: # 방문한 적 없으면
visited.append(n)
# print("인접 노드들:", graph[n])
temp = list(set(graph[n]) - set(visited))
temp.sort(reverse=True)
stack += temp
# print("stack:", stack)
print(*visited)
def bfs(graph, start):
visited = []
queue = [start]
while queue: # 큐가 빌 때까지
n = queue.pop(0)
if n not in visited: # 방문한 적 없으면
visited.append(n)
near_list = list(set(graph[n]) - set(visited)) # set은 정렬이 보장되지 않는다
# print("n:", n, ", 연결된 노드:", near_list)
near_list.sort()
queue += near_list
# print("queue:", queue)
print(*visited)
from sys import stdin
def dfs(graph, start):
visited = []
stack = [start]
while stack:
n = stack.pop()
if n not in visited:
visited.append(n)
temp = list(set(graph[n]) - set(visited))
temp.sort(reverse=True)
stack += temp
print(*visited)
def bfs(graph, start):
visited = []
queue = [start]
while queue:
n = queue.pop(0)
if n not in visited:
visited.append(n)
near_list = list(set(graph[n]) - set(visited))
near_list.sort()
queue += near_list
print(*visited)
n, m, v = map(int, stdin.readline().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
x, y = map(int, stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
dfs(graph, v)
bfs(graph, v)
set
사용 시 정렬이 보장되지 않는다.
bfs
함수에서 set
으로 받은 인접 노드들이 정렬되지 않았던 반례 때문에 틀렸습니다의 연속이었다. 위 코드처럼 노드들을 sort
로 정렬해주면 해결할 수 있다.