그래프의 개념을 이해하고 이를 실제 코드로 구현할 수 있습니다. 구현 그래프를 탐색하고 최단 경로를 구할 수 있습니다.
1편은 그래프의 개념입니다.
총 3편으로 준비했습니다.
1. 그래프의 개념
2. 그래프 탐색
3. 그래프 몸풀기 문제
자료구조에서 데이터를 어떻게 구축할지 고민한다면, 알고리즘에서는 자료구조에서 어떤 순서와 방식으로 탐색할지를 고민합니다. 그래프에서 경로를 찾는다고 할 때 경로를 찾는 방법은 다음과 같이 크게 2가지가 있습니다.
- 더 이상 탐색할 노드가 없을 때까지 일단 가봅니다. 그러다가 더 이상 탐색할 노드가 없으면 최근에 방문했던 노드로 되돌아간 다음 가지 않은 노드를 방문합니다(깊이 우선 탐색).
- 현재 위치에서 가장 가까운 노드부터 모두 방문하고 다음 노드로 넘어갑니다. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문합니다(너비 우선 탐색).
글로만 보면 단번에 이해하기 어려울 겁니다. 이 두 방법으로 A부터 E까지 탐색하는 과정을 그림으로 나타냈습니다. 하나씩 보며 설명하겠습니다.
우선 깊이 우선 탐색부터 살펴봅시다.
01단계 노드 A에서 노드 D까지 차례대로 방문합니다. 노드 D까지 방문하면 더 방문할 곳이 없습니다(막힘).
02단계 노드 D에서 B로 돌아옵니다. 여기서 다시 끝까지 갑니다. 즉, 노드 E까지 갑니다.
03단계 다시 노드 E → B → A 순으로 돌아옵니다. 그다음 끝까지, 노드 C까지 갑니다. A → B → D → E → C 순서로 모든 노드를 방문했습니다.
다음은 너비 우선 탐색입니다.
01단계 노드 A에서 가장 가까운 노드 B, C를 방문합니다.
02단계 노드 B에서 가장 가까운 노드 D, E를 방문합니다. A→ B → C → D → E로 모든 노드를 방문했습니다. 그럼 대략적인 탐색 방식을 살펴봤으니 각각의 방식을 제대로 공부해보겠습니다.
깊이 우선 탐색
이 우선 탐색(Depth-first Search, DFS)은 앞서 본 것처럼 시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문합니다. 최대 깊이 노드까지 방문한 다음에는 이전에 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 최대 깊이까지 차례대로 방문합니다.
탐색을 하려면 일단 시작 노드를 정하고, 스택에 시작 노드를 푸시합니다. 스택에 있는 노드는 아직 방문하지 않았지만 방문할 예정인 노드입니다. 시작 노드를 푸시했으면 다음 과정을 반복합니다.
진행 1 스택이 비었는지 확인합니다. 스택이 비었다는 건 방문할 수 있는 모든 노드를 방문했음을 의미합니다. 따라서 스택이 비었으면 탐색을 종료합니다.
진행 2 스택에서 노드를 팝합니다. 팝한 원소는 최근에 스택에 푸시한 노드입니다.
진행 3 팝한 노드의 방문 여부를 확인합니다. 아직 방문하지 않았다면 노드를 방문 처리합니다.
진행 4 방문한 노드와 인접한 모든 노드를 확인합니다. 그리고 그 중에서 아직 방문하지 않은 노드를 스택에 푸시합니다. 스택은 FILO 구조이므로 방문 순서를 오름차순으로 고려한다면 역순으로 노드를 푸시해야 합니다.
이 과정을 코드로 구현할 때 다음 세 가지 사항을 고려해야 합니다.
고려 1 탐색할 노드가 없을 때까지 간선을 타고 내려갈 수 있어야 합니다.
고려 2 가장 최근에 방문한 노드를 알아야 합니다.
고려 3 이미 방문한 노드인지 확인할 수 있어야 합니다.
깊이 우선 탐색의 핵심은 ‘가장 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인한다’입니다.
탐색하고 있는 방향의 역방향으로 되돌아가는 동작을 백트래킹(Back Tracking)이라고 합니다. 스택은 최근에 푸시한 노드를 팝할 수 있으므로 특정 노드를 방문하기 전에 최근 방문 노드를 팝 연산으로 쉽게 확인할 수 있습니다. 이런 스택의 특성을 활용하여 백트래킹 동작을 쉽게 구현한 것입니다.
스택을 활용하여 깊이 우선 탐색을 구현해보는 방법을 알아봅시다.
스택을 활용한 깊이 우선 탐색
선입후출의 특성을 가진 스택으로 가장 최근에 방문한 노드를 확인할 수 있습니다. 자세한 내용은 그림과 함께 봐야 이해하기 쉽습니다. 스택을 활용한 깊이 우선 탐색 과정을 살펴봅시다.
01단계 스택에는 방문 예정인 노드를 푸시합니다. 시작 노드는 당연히 방문해야 할 노드이므로 1을 스택에 넣습니다. 스택에 푸시한 노드는 파란색, 방문한 노드는 회색으로 색칠하겠습니다. 아직 1은 방문하지 않았고, 방문할 예정이기만 하므로 그래프는 아무것도 색칠하지 않았습니다.
02단계 이제 1에 방문할 차례입니다. 1을 팝한 후에 1이 방문한 상태인지 확인합니다. 1은 아직 방문하지 않은 노드이므로 이제 방문 처리를 합니다(그래프의 노드 1을 색칠합니다). 방문 처리를 한 후에는 1과 인접하면서 방문하지 않은 노드 4, 5를 5 → 4 순서로 푸시하여 이후 4 → 5 순서로 방문 처리할 수 있게 합니다.
※ 이렇게 스택에 역순으로 푸시하면 의도한 대로 방문 처리를 할 수 있습니다.
03단계 이제 같은 방식으로 팝, 푸시를 진행합니다. 스택에서 4를 팝한 다음, 4가 방문한 상태인지 확인합니다. 4는 아직 방문하지 않았으므로 방문 처리합니다. 그런 다음 4와 인접한 2, 3을 3 → 2 순서로 푸시합니다.
04단계 2를 팝합니다. 2는 방문하지 않았으므로 2를 방문 처리합니다. 그런 다음 2와 인접하면서 방문하지 않은 노드 3을 푸시합니다.
05단계 이후 작업도 마찬가지입니다. 3을 팝하고 방문 처리합니다. 3과 인접한 노드는 없으니 아무것도 푸시하지 않습니다.
06단계 또 다시 3을 팝할 때는 이미 방문 처리를 했으므로 아무 작업도 하지 않습니다.
07단계 5를 팝하고, 5를 방문 처리합니다. 스택이 비었으므로 작업이 끝났습니다.
재귀 함수를 활용한 깊이 우선 탐색
스택을 직접 사용하지 않고도 깊이 우선 탐색을 구현할 수도 있습니다. 바로 재귀 함수를 활용하는 것입니다. 재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 깊이 우선 탐색에 활용할 수 있는 것입니다. 호출할 함수는 dfs( )라 선언하고 dfs(N)을 호출하면 다음 동작을 하도록 구현했다고 가정하겠습니다.
※ 여기서는 인접한 노드를 방문할 때 숫자가 낮은 노드부터 탐색하는 방식으로 설명했습니다.
- dfs(N) : N번 노드를 방문 처리하고 N번 노드와 인접한 노드 중 아직 방문하지 않은 노드를 탐색
01단계 시작 노드는 1번 노드이므로 dfs(1)을 호출합니다. dfs(1)이 실행되면 1을 방문 처리하고 내부적으로 dfs(4)를 재귀 호출합니다. 아직 dfs(1)은 dfs(4)를 호출한 상태이므로 종료되지 않습니다. 따라서 스택에 dfs(1)이 쌓입니다.
02단계 dfs(4)가 실행되므로 4는 방문 처리하며, 내부적으로 dfs(4)는 dfs(2)를 호출합니다. 같은 이유로 dfs(4)는 스택에 쌓입니다.
03단계 dfs(2)를 실행합니다. 2를 방문 처리하고 dfs(2)는 dfs(3)을 재귀 호출합니다.
04단계 dfs(3)을 실행합니다. 3은 인접 노드가 없으므로 추가로 재귀 호출을 하지 않고 함수를 종료합니다. 여기서 처음으로 스택에서 빠져나오는 함수가 생깁니다. 그림을 자세히 보기 바랍니다.
05단계 스택 특성에 의해 dfs(2)로 돌아가 다음 실행 스텝을 진행합니다. 그러나 2는 인접한 노드가 없으므로 종료됩니다.
06단계 dfs(4)로 돌아가 다음 실행 스텝을 진행합니다. 4도 인접 노드가 없습니다. 함수를 종료합니다. 2의 다음 노드인 3이 인접하므로 탐색을 시도해보지만, 3은 이미 방문한 노드입니다. 변경된 부분 없이 해당 함수가 종료 됩니다.
07단계 dfs(1)의 다음 실행 스텝을 진행합니다. 1은 5와 인접해 있으므로 dfs(5)를 재귀 호출합니다.
08단계 dfs(5)를 실행합니다. 5를 방문 처리하고 5와 인접한 노드가 없으므로 dfs(5)를 종료합니다. dfs(1)도 이어 종료합니다.
너비 우선 탐색
너비 우선 탐색(Breadth first Search, BFS)은 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘입니다. 여기서 말하는 거리는 시작 노드와 목표 노드까지의 차수입니다. 간선 가중치의 합이 아닌 것에 주의합시다. 탐색을 하려면 일단 시작 노드를 정하고, 스택에 시작 노드를 푸시합니다. 시작 노드를 큐에 푸시하면서 방문 처리를 합니다. 큐에 있는 노드는 이미 방문 처리했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태라고 생각하면 됩니다. 이후 다음 과정을 반복합니다.
진행 1 큐가 비었는지 확인합니다. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했다는 의미입니다(탐색 종료).
진행 2 큐에서 노드를 팝합니다.
진행 3 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드를 큐에 푸시하며 방문 처리합니다.
이 과정을 코드로 구현할 때 다음 두 가지 사항을 고려해야 합니다.
고려 1 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 합니다.
고려 2 이미 방문한 노드인지 확인할 수 있어야 합니다.
너비 우선 탐색 방식을 보면 시작 노드부터 인접한 노드를 모두 방문한 후 그다음 단계의 인접 노드를 방문합니다. 즉, 먼저 발견한 노드를 방문합니다. 이러한 특성 때문에 너비 우선 탐색을 할 때는 큐를 활용합니다. 이 역시 구체적인 내용은 그림을 보며 이해해봅시다. 그림으로 제시한 그래프는 깊이 우선 탐색과 같고, 스택이 아닌 큐로 구현하는 점에만 주목합시다.
큐를 활용한 너비 우선 탐색
01단계 시작 노드 1을 큐에 푸시하고 방문 처리합니다.
02단계 1을 팝한 후 인접한 4와 5를 봅니다. 아직 방문하지 않았으므로 방문 처리하고 4, 5 순서로 큐에 푸시합니다.
03단계 4를 팝한 후 인접한 2와 3을 봅니다. 아직 방문하지 않았으므로 방문 처리하고 2, 3 순서로 큐에 푸시합니다.
04단계 5를 팝한 후 인접한 1과 4를 봅니다. 이미 방문했으므로 아무것도 하지 않습니다. 큐의 나머지 노드들도 자신과 인접한 노드들을 모두 방문했으므로 아무것도 하지 않고 팝합니다. 큐가 비면 탐색을 마무리한 것입니다.
깊이 우선 탐색과 너비 우선 탐색 비교
깊이 우선 탐색과 너비 우선 탐색은 모두 탐색 알고리즘이므로 겉으로 봤을 때는 차이가 없는 것 같다고 느끼기 쉽습니다만 두 알고리즘의 차이는 분명합니다. 깊이 우선 탐색은 깊게 탐색 후 되돌아오는 특성이 있고, 너비 우선 탐색은 가중치가 없는 그래프에서 최단 경로를 보장합니다. 이 차이를 확실하게 알아야 코딩 테스트에서 요긴하게 써먹을 수 있습니다.
깊이 탐색 후 되돌아오는 깊이 우선 탐색
깊이 우선 탐색은 가장 깊은 곳을 우선하여 탐색하고, 더 이상 탐색할 수 없으면 백트래킹하여 최근 방문 노드부터 다시 탐색을 진행한다는 특징이 있어서 모든 가능한 해를 찾는 백트래킹 알고리즘을 구현할 때나 그래프의 사이클을 감지해야 하는 경우 활용할 수 있습니다. 코딩 테스트에서는 탐색을 해야 할 때, 최단 경로를 찾는 문제가 아니면 깊이 우선 탐색을 우선 고려해보는 것이 좋습니다.
최단 경로를 보장하는 너비 우선 탐색
앞서 깊이 우선 탐색과는 반대로 너비 우선 탐색은 찾은 노드가 시작 노드로부터 최단 경로임을 보장합니다. 왜냐하면 시작 노드로부터 직접 간선으로 연결된 모든 노드를 먼저 방문하기 때입니다. 쉽게 말해 문제에 대한 답이 많은 경우 너비 우선 탐색은 이 답 중에서도 가장 가까운 답을 찾을 때 유용합니다. 그래서 너비 우선 탐색은 미로 찾기 문제에서 최단 경로를 찾거나, 네트워크 분석 문제를 풀 때 활용할 수 있습니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
