:: 그래프 탐색 ::
dfs와 bfs알고리즘은 대표적인 그래프 탐색 알고리즘이다.
해당 알고리즘은 코딩 테스트에 높은 비율로 출제되기 때문에 꼭 학습해야하는 알고리즘 중 하나이다.
DFS(Depth First Search) - 깊이 우선 탐색
깊이 우선 탐색은 재귀를 통하여, 시작 노드부터 그래프의 제일 안쪽 노드까지 깊숙히 방문하며 그래프를 탐색하는 알고리즘이다.
다음 그림 예시를 통해 탐색과정에 대하여 알아보자
1번에서 시작하는 다음과 같은 그래프가 있다고 하자. 그래프는 수가 작은 순으로 탐색하도록 초기 값이 주어진다.
그럼 DFS로 탐색하게 되었을 때, 어떻게 탐색하게 될까?
노드에 방문할 때마다 해당 노드에 방문 처리를 하며, 1과 연결되어 있는 노드2와 노드3 중에 수가 작은 순으로 탐색을 시작하기 때문에 2번부터 탐색한다.
깊이 우선 탐색은 말 그대로 깊게 파고드는 방식으로 탐색하는 방식이기 때문에
2번 노드 다음으론 7번 노드를 탐색한다.
7번 노드에 도착하면, 7번 노드와 연결된 6번 노드와 8번 노드가 주어진다.
다음과 같은 상황에선 두 가지 방향이 있지만, 그래프는 작은 수를 먼저 탐색하도록 값이 주어졌다고 가정했기 때문에 6번을 탐색한다.
6번에 도착하면 다음 깊이에 있는 노드는 존재하지 않는다.
이러한 경우엔 방문 처리 후, 더이상 재귀하지 않아 재귀를 끝내고 이전 dfs함수로 돌아가게 되는데
이전 노드에선 선택지가 6,8 두 가지가 있었고 6은 방금 방문하였으므로 8을 탐색한다.
다음으로 도착한 8번 노드는 1번, 7번 노드와 연결되어 있다.
하지만 두 가지 노드 모두 이미 방문한 적이 있다.
해당 경우는 오른쪽에 있는 노드들을 모두 탐색하였으므로, 줄줄이 재귀를 끝내며 노드1 까지 쭉 돌아가게 될 것이다.
노드1은 2번, 3번, 8번 노드와 연결되어 있었고 2번은 방금 방문하였으니 3번 노드로 이동하게 되며, 그 뒤론 값이 작은 순서대로 4,5번 노드를 방문하며 탐색을 마치게 될 것이다. (8번 노드는 이미 방문하였으므로 skip)
그럼 최종적으로 DFS 탐색 알고리즘으로 방문한 노드의 순서는
1-2-7-6-8-3-4-5
이다.
이제 방금 배운 DFS 알고리즘을 코드를 통해 확인해보자.
# 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]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)
DFS 함수의 매개변수는 (그래프, 현재 노드, 방문기록) 으로 설정한다.
DFS 함수는 노드 갯수 만큼의 크기를 가진 visited array를 통해 True,False로 방문 체크를 진행한다.
또한 graph[현재 노드] 를 통해 알 수 있는 현재 노드와 연결된 다른 노드의 번호를 체크하여 방문하지 않은 곳이라면, dfs함수 호출을 통해 연결된 노드들을 줄줄이 방문체크 한다.
만약 방문 체크가 되어있다면 방문하지 않는다.
이와 같은 방식이 바로 DFS 탐색방식이다.
BFS(Breadth First Search) - 너비 우선 탐색
너비우선 탐색인 BFS 알고리즘은 주변 노드를 확인하며 탐색하는 알고리즘이다.
한 노드의 끝까지 갔다 돌아오는 DFS 와는 다르게 주변 노드를 탐색하며 FIFO 구조를 가진 큐(Queue)를 사용한다는 점이 특징이다.
모든 방향으로 순차적으로 뻗어나기기 때문에, 특정 노드까지의 최단경로를 구하는 데에도 유용한 알고리즘이다.
예시를 통해 알고리즘이 어떻게 그래프를 탐색하는 지 이해해보자.
시작은 DFS와 같이 노드1에서 시작한다.
그리고 1의 주변 노드들로 뻗어나가게 되는데, 작은 숫자인 2번, 3번, 8번 순으로 Queue에 담고 하나씩 탐색한다.
다음으로 2,3,8번 노드를 탐색하면서 각 노드의 주변 노드인 7,4,5번 노드를 queue에 담는다.
작은 숫자부터 Queue에 담았다가 꺼내어 탐색하기 때문에
2의 주변 노드인 7,
8의 주변 노드는 7이지만 이미 queue에 담았음,
3의 주변 노드인 4,5
순으로 Queue에 담기고 탐색된다.
마지막으로 7의 주변 노드인 6을 Queue에 담고 탐색하면 모든 노드를 탐색한 것이 된다.
이제 방금 이해한 BFS 알고리즘을 코드를 통해 알아보자
from collections import deque
# BFS 메서드 정의
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],
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9
# 정의된 BFS 함수 호출
bfs(graph, 1, visited)
bfs 함수는 (그래프, 시작 노드, 방문 기록) 을 매개변수로 받아 구현되는데,
처음에 시작 노드를 Queue에 담고 방문 체크를 한 뒤에 해당 큐를 이용하여 탐색을 시작한다.
왜 List가 아니라 deque를 사용하나요?
Queue는 List가 아닌 Collections의 deque 라이브러리를 사용하여 구현하는 것이 일반적이다.
List를 이용하면 append 연산에 O(n) 만큼의 시간복잡도가 소요되지만 덱(deque) 라이브러리를 사용하면 O(1) 만큼의 작은 시간 복잡도만 요구된다.
다시 본론으로 돌아가서 탐색은 Queue가 빌때까지 탐색한다.
모든 노드를 탐색하게 되면 방문하지 않은 곳이 없어 더이상 큐에 노드를 담지 않아 queue가 비게 되어 반복이 끝나기 때문이다.
graph[현재노드] 를 통해 알 수 있는 현재 노드와 연결된 아직 방문하지 않은 모든 노드를 queue에 삽입하고 방문체크를 반복하는 과정을 통해 bfs 방식으로 그래프 탐색을 구현할 수 있다.
해당 알고리즘을 학습하는 과정에서 계속해서 두 방식이 헷갈려 아래 reference에 참고한 영상을 10번도 넘게 봤던 것 같다.
결과적으로 그래프 탐색에서 너비와 깊이 라는 것이 무엇을 의미하는지 정확히 이해할 수 있었고, 알고리즘 문제 해결에 유용하게 사용하고 있다.
reference
https://www.youtube.com/watch?v=7C9RgOcvkvo
'코딩테스트 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 에라토스테네스의 체 with '프로그래머스 2단계 - 소수찾기 문제' (0) | 2023.02.22 |
|---|