그래프 알고리즘 소개
시뮬레이션
알고 있어야 하는 내용
자주 사용하는 모듈(collections.deque)
그래프
개념
그래프는 정점과 간선으로 이루어진 자료구조입니다. 정점은 버텍스(vertex), 노드(node)라고 부르기도 하고, 간선은 엣지(edge), 링크(link)라고 부르기도 합니다.
그래프는 간선이 방향을 가지고 있냐에 따라 무방향 그래프(양방향 그래프), 방향 그래프(단방향 그래프) 나뉩니다.
정점은 데이터를 가지고 있고, 간선은 정점과의 관계를 나타냅니다. 우리가 알고리즘 문제를 풀 때 보통 위치 데이터와 해당 위치가 가지고 있는 값을 데이터로 가지고 있습니다.
무방향 그래프(양방향 그래프)는 정점 A와 정점 B가 연결되어 있으면 정점 B에서 정점 A로 갈 수 있고, 반대로 정점 A에서 정점 B로도 갈 수 있습니다. 하지만 단방향 그래프는 정점 A에서 정점 B로 갈 수 있지만, 정점 B에서 정점 A로 가지 못합니다.
좀 더 우리가 문제를 풀 때 필요한 예시를 들어보겠습니다.
예시
2차원 리스트로 표현되어 있고, 상하좌우로 움직일 수 있는 미로를 생각해봅시다. 이때 미로는 벽으로 둘러싸여 있고, 갈 수 있는 곳은 0, 벽으로 막혀 있는 곳은 1이라고 표현한다고 합니다.
이렇게 3x3 미로가 있다면 바깥쪽 부분은 벽으로 둘러싸여 있고, 흰 칸은 움직일 수 있는 칸, 검은 칸은 벽이라고 해봅시다. 여기서 (0, 0)에서 (2, 2)로 가는 최단 거리는 2가지 방법이 있습니다.
해당 미로를 간선과 노드로 그려보면 아래 그림과 같습니다.
(1,1)은 벽이므로 어느 좌표에서든 벽으로 갈 수는 없으니 (1,1)과 연결된 간선이 없습니다. 그리고 (1, 0)은 (1, 0)에서 (0, 0)으로 갈 수도 있고, (2, 0)으로도 갈 수 있으니 무방향 그래프로 표현됩니다.
이 그래프도 마찬가지로 최단 거리가 2가지가 있습니다. 빨간색 노드가 이동하는 간선입니다.
탐색 방법
그래프 알고리즘의 단순 탐색 알고리즘은 2가지가 있습니다.
너비 우선 탐색(Breadth First Search, BFS)
깊이 우선 탐색(Depth First Search, DFS)
삼성 역량 테스트와 삼성 A형에서 그래프 알고리즘 문제는 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 알고리즘만을 사용한 문제가 나옵니다.
여기에서는 BFS와 DFS 알고리즘을 자세하게 배우지는 않을 것이고, 어떤 방식을 이용하는지 알려드리겠습니다.
예시는 위에 언급한 3x3 미로로 예시를 들겠습니다.
너비 우선 탐색
Breadth First Search 줄여서 BFS라고 부르는 알고리즘입니다. 작동 방식은 시작 지점에서 가장 가까운 정점부터 전부 방문하고, 그 이후에는 그다음으로 시작 지점에 가까운 정점들을 전부 방문하는 것을 반복하는 방식입니다.
C++에서는 queue를 사용하고, Python에서는 collections.deque 모듈을 사용하여 큐를 사용하게 됩니다.
일단 미로는 (0, 0)에서 시작하니 큐에는 (0, 0)이 들어있을 것입니다.
이제 큐에서 (0, 0)을 빼고, (0, 0)에서 가장 가까운 좌표를 찾아봅시다.
(0, 0)에서 갈 수 있는 가장 가까운 위치는 (0, 1)과 (1, 0)이 있습니다. 이 좌표들을 큐에 넣어줍시다. (0, 1), (1, 0)으로 큐에 넣든, (1, 0), (0, 1)로 큐에 넣든 상관없습니다.
이제 큐의 맨 앞에 있는 값인 (0, 1)빼고 (0, 1)과 가장 가까운 좌표를 찾아서 큐에 넣어봅시다.
(0, 1)과 가장 가까운 좌표는 (0, 0)과 (0, 2)인데 (0, 0)은 이미 방문했으니 큐에 넣을 좌표는 (0, 2) 밖에 없습니다. (0, 2)를 큐에 넣어줍시다.(왼쪽 그림)
이제 (1, 0)을 큐에서 빼고 (1, 0)과 가장 가까운 좌표를 찾아봅시다.
(1, 0)과 가장 가까운 좌표는 (0, 0)과 (2, 0)이 있는데 (0, 0)은 이미 방문했으니 (2, 0)만 큐에 넣어주면 됩니다.(오른쪽 그림)
마찬가지로 큐에서 (0, 2)를 뺀 후에 (1, 2)를 넣고, 큐에서 (2, 0)을 뺀 후에 (2, 1)을 넣어주었다고 합시다. (왼쪽 그림)
큐에서 (1, 2)를 빼고, 아직 방문하지 않은 좌표 중에서 가장 가까운 좌표인 (2, 2)를 큐에 넣어주면 됩니다. (오른쪽 그림)
이제 큐에서 (2, 1)과 (2, 2)를 뽑아도 모든 정점을 방문했으니 더 이상 큐에 넣을 좌표가 없게 됩니다. 그래서 둘 다 큐에서 빼주기만 하면 BFS 알고리즘이 끝나게 됩니다.
트리 자료구조로 BFS 동작 과정을 그려보면 더 이해하기가 쉽습니다.
이렇게 깊이가 1인 루트 노드부터 방문하고, 깊이가 2인 노드들, 깊이가 3인 노드들을 방문하게 됩니다.
왜 너비 우선 탐색이라고 부르고 있는지 알 수 있습니다.
깊이 우선 탐색
Depth First Search 줄여서 DFS라고 부르는 알고리즘입니다. 작동 방식은 BFS와 다르게 어떤 노드에서 가장 가까운 노드를 하나 정하면 갈 수 있는 곳까지 전부 가보는 알고리즘입니다. 매 노드마다 가장 가까운 노드를 하나 정해서 갈 수 있는 곳까지 가보고, 그 이후에 다른 노드를 정해서 갈 수 있는 곳까지 가보는 방식을 반복하기 때문에 재귀 함수를 사용하거나 스택을 사용하는 편입니다. 보통 재귀 함수를 사용합니다.
미로의 시작점은 (0, 0)이므로 (0, 0)에서 가장 가까운 좌표는 (0, 1)과 (1, 0)이 있습니다. 여기서 우리는 (0, 1)을 정해서 끝까지 가보겠습니다.
(0, 1)에서 가장 가까운 정점은 (0, 2)이고, (0, 2)에서 가장 가까운 정점은 (1, 2)이고, (1, 2)에서 가장 가까운 정점은 (2, 2)가 됩니다. (2, 2)는 미로의 출구이므로 재귀 함수가 종료하게 됩니다.
이제 뒤로 돌아가서 하나하나 살펴봅시다. (2, 2)의 이전 노드는 (1, 2)인데, (1, 2)에서 더 방문할 노드가 없습니다. 더 뒤로 돌아갑니다. (0, 2)에서 더 방문할 노드가 없습니다. 뒤로 돌아갑니다. (0, 1)에서도 더 방문할 노드가 없습니다. 뒤로 돌아가서 (0, 0)이 됩니다.
(0, 0)에서 방문할 수 있는 노드는 (1, 0)이 있습니다. 이제 (1, 0)에서 출발하여 끝까지 가보겠습니다.
(1, 0) → (2, 0) → (2, 1)이 됩니다. 이제 (2, 1)에서는 더 방문할 노드가 없습니다. 뒤로 돌아갑니다. (2, 0)에서도 더 방문할 노드가 없습니다. 뒤로 돌아갑니다. (1, 0)에서도 더 방문할 노드가 없습니다. 뒤로 돌아가 (0, 0)이 됩니다. (0, 0)에서도 마찬가지로 방문할 노드가 없습니다. 그러면 이제 재귀 함수가 끝나게 됩니다.
DFS 역시 마찬가지로 트리 자료구조를 이용하면 이해하기가 더 쉽습니다.
BFS와 DFS를 트리로 그려본 것을 하나로 합쳐보면 아래 그림과 같습니다.
이 그림에서는 DFS가 더 많은 과정을 거치지만 그렇다고 일반적인 상황에서도 DFS가 BFS보다 느린 것은 아니고, 그래프가 어떻게 되어 있냐에 따라 DFS가 더 빠를 수도 있고, BFS가 더 빠를 수도 있게 됩니다.
Last updated
