📜문제 설명
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
📍입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
4 5 1
1 2
1 3
1 4
2 4
3 4📍출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
1 2 4 3
1 2 3 4📄문제 해결
📝내가 푼 코드
1차 시도
# edge 추가
def add_edge(graph, u, v):
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append(v) # u -> v
graph[v].append(u) # v -> u (양방향)
# 스택으로 DFS 탐색
def dfs(graph, start):
visited = []
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
print(node, end=' ')
# 스택은 리스트의 맨 뒷 값을 가져오며 탐색하기에 작은 노드부터 탐색하기 위해 내림차순으로 정렬한다
stack += sorted(graph[node], reverse=True)
# 큐로 BFS 탐색
def bfs(graph, start):
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node, end=' ')
queue += sorted(graph[node])
N, M, V = map(int, input().split(' '))
graph = {}
for _ in range(M):
u, v = map(int, input().split(' '))
add_edge(graph, u, v)
dfs(graph, V)
print()
bfs(graph, V)DFS와 BFS 개념이 흐릿해져서 다른 자료를 함께 보면서 코드를 짰다. 문제 자체가 조건에 맞춰서 DFS와 BFS 탐색을 해봐라! 인 것 같아서 이번 기회에 제대로 공부해보자는 마음으로 코드를 따라 작성했다.
방문하지 않은 노드가 여러 개일 때, 작은 값인 노드를 선택할 것! 이라는 조건에 맞춰 stack과 queue에 노드별로 연결된 노드를 추가할 때도 sorted()를 활용해 맞는 답을 낼 수 있도록 고려하였다. 그런데, 왜인지 잘 채점되던 중 런타임 에러가 발생했다.
2차 시도 -> 성공
# 스택으로 DFS 탐색
def dfs(graph, start):
visited = []
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.append(node)
print(node, end=' ')
# 스택은 리스트의 맨 뒷 값을 가져오며 탐색하기에 작은 노드부터 탐색하기 위해 내림차순으로 정렬한다
stack += sorted(graph[node], reverse=True)
# 큐로 BFS 탐색
def bfs(graph, start):
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
print(node, end=' ')
queue += sorted(graph[node])
N, M, V = map(int, input().split(' '))
graph = {n:[] for n in range(1, N+1)}
for _ in range(M):
u, v = map(int, input().split(' '))
graph[u].append(v) # u -> v
graph[v].append(u) # v -> u (양방향)
dfs(graph, V)
print()
bfs(graph, V)문제는 간선이 없는 노드가 graph 변수에 들어가지 않았기 때문이었다. 그냥 생각없이 입력받은 간선에 따라 graph를 연결리스트 형대로 만들도록 하는 함수를 사용하였는데, 노드가 1, 2, 3이 있을 때 1이 시작점임에도 2, 3과 연결이 되어있지 않다면 graph 변수에는 아예 값이 들어가지 않아 KeyError가 발생하게 되는 것이었다.
따로 함수를 사용하지 않고, graph의 초기값을 설정할 때 입력받은 N을 활용해 모든 노드에 대해서 노드 번호를 key로, 빈 리스트를 value로 초기화해주는 방식을 활용하니 문제가 해결되었다.
🤔느낀점
오늘 문제를 풀면서 DFS와 BFS를 언제 마지막으로 공부했는지 찾아보았다. 그에 관한 기록이 이 블로그에 있었는데, 거의 9개월 전에 공부하고 그 뒤로 꺼내보지 않았더니 오늘 새까맣게 까먹어버린 스스로를 보면서 역시 공부는 꾸준히 복습을 해주어야 잊어먹지 않는다는 것을 새삼스럽게 깨달을 수 있었다.
