문제 설명
그래프에 대한 노드, 간선 정보가 주어지고 DFS, BFS로 그래프 탐색 결과를 출력하는 문제이다. 일반적으로 DFS는 재귀, BFS는 큐 방식으로 구현한다. 이전에 책으로 공부하면서 간단한 구현을 하는 방법에 대해서 알고 있어서 크게 어렵지 않을거라고 생각했는데 푸는데 생각보다 어려움이 있었다.(정답율이 생각보다 낮은 이유가 있었다..)
답을 도출하기 전에 이전에 책으로 공부하면서 구현했는 DFS, BFS 코드를 먼저 보자
DFS, BFS 구현 예제
# dfs
def dfs(graph, v, visited):
visited[v] = True
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
dfs(graph, 1, visited)
# bfs
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [False] * 9
bfs(graph, 1, visited)해당 예제는 '이것이 코딩 테스트다 with python' 책에서 나온 구현방법이며 가장 기본적인 형태를 가지고 있다.
문제와 다른 점은 그래프에 대한 정보가 어떻게 주어지는지이다.
# 예제
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
# 문제
graph = [
[1, 2],
[1, 3],
[1, 4],
[2, 4],
[3, 4]
]
- 예제는
graph[i][:]로 i번째 노드가 몇번 노드와 연결되어있는지 정보가 나열되어있다. - 문제는 2차원 배열로 하나의 요소가 연결된 어떤 노드끼리 연결되어 있는지 정보가 나열되어있다.
문제 상황
그래서 리스트 컴프리헨션으로 list = [i[1] for i in graph if i[0] == v] 해당 노드가 연결되어 있는 노드의 정보를 추출해서 비슷한 방식으로 풀려고 했으나 당연히 되지 않았다.
(여기서 v는 시작 노드이며 i[1]을 추출해 해당 노드가 어떤 노드와 연결되어있는지 추출해 배열로 만들었다.)
- 왜냐하면 각 요소의 i[0]가 아닌 i[1]인 경우는 고려하지 않기 때문이다.
- 예를 들어 [1, 4], [2, 1] 처럼 있다고 가정하자 위와 사실상 '1'노드는 '2', '4'와 연결되어있는데 위와 같이 코드를 작성하면 '2' 노드에 방문을 하지 못한다.
해결 방법
입력 받은 노드의 연결 정보에서 각 요소의 위치를 바꿔 graph에 추가해준다. 코드로 보면 다음과 같다.
# 기존 정보
graph = [
[1, 2],
[1, 3],
[1, 4],
[2, 4],
[3, 4]
]
# 위치 변경
change_location = [
[2, 1],
[3, 1],
[4, 1],
[4, 2],
[4, 3]
]
# 최종 결과
result = [
[1, 2],
[1, 3],
[1, 4],
[2, 4],
[3, 4],
[2, 1],
[3, 1],
[4, 1],
[4, 2],
[4, 3]
]이처럼 위치를 바꾼정보를 탐색할 정보 리스트에 합쳐주면 해결할 수 있다. 어짜피 재방문한 경우 코드 상에서 dfs 메서드를 호출하지 않도록 구현하기 때문에 제대로 동작하는걸 확인할 수 있었다.
정답 코드
# DFS와 BFSfrom collections import deque
n, m, v = map(int, input().split())
graph = []
for i in range(m):
graph.append(list(map(int, input().split())))
visited_dfs = [False] * (n + 1)
visited_bfs = [False] * (n + 1)
list_1 = [i[0] for i in graph]
list_2 = [i[1] for i in graph]
for i in range(m):
graph.append([list_2[i], list_1[i]])
def dfs(v):
visited_dfs[v] = True
print(v, end=' ')
list = [i[1] for i in graph if i[0] == v]
list.sort()
for i in list:
if not visited_dfs[i]:
dfs(i)
def bfs(v):
queue = deque([v])
visited_bfs[v] = True
while queue:
v = queue.popleft()
print(v, end=' ')
list = [i[1] for i in graph if i[0] == v]
list.sort()
for i in list:
if not visited_bfs[i]:
queue.append(i)
visited_bfs[i] = True
dfs(v)
print()
bfs(v)입력 값의 위치변환 후 병합
list_1 = [i[0] for i in graph]
list_2 = [i[1] for i in graph]
for i in range(m):
graph.append([list_2[i], list_1[i]]) dfs
def dfs(v):
visited_dfs[v] = True
print(v, end=' ')
list = [i[1] for i in graph if i[0] == v]
list.sort()
for i in list:
if not visited_dfs[i]:
dfs(i)
- 시작 위치에서의 값으로 연결된 노드의 정보를 리스트로 추출하고
sort함수를 통해 정렬한다.(왜냐하면 문제에서 작은 수부터 방문하라고 했기 때문이다.) - 그리고 이전에 알던 구현 방법으로 재귀호출을 통해 그래프 탐색을 한다.
bfs
def bfs(v):
queue = deque([v])
visited_bfs[v] = True
while queue:
v = queue.popleft()
print(v, end=' ')
list = [i[1] for i in graph if i[0] == v]
list.sort()
for i in list:
if not visited_bfs[i]:
queue.append(i)
visited_bfs[i] = True - dfs와 마찬가지로 시작 위치에서 연결된 노드를 추출하고 queue를 사용하여 bfs를 구현
