섬 연결하기 (Level 3)
문제
코딩테스트 연습 - 섬 연결하기
4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4
programmers.co.kr
접근법
최소 비용 신장 트리
이번 문제는 두 가지 방법으로 풀었다. 처음 접근하는 방법은 동일하고 구현하는 방법에서 차이가 있기 때문에 공통된 부분을 설명한 뒤 두 가지 풀이법을 모두 다뤄본다.
문제에서 요구하는 바는 모든 섬을 가장 적은 비용으로 연결했을 때의 비용이다. 이를 자료구조에서는 최소 비용 신장 트리 (MST)라고 한다. 이에 대한 설명은 예전에 다룬 글이 있어 링크를 남긴다. 간략하게만 정리하면 최소 비용 신장 트리는 신장 트리의 일종인데, 먼저 신장 트리가 되기 위해서는 다음의 조건을 만족해야 한다.
- 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.
- 그래프 내에서 사이클을 형성하지 않는다.
최소 비용 신장 트리는 만들 수 있는 여러 신장 트리들 중 간선 비용합이 가장 작은 신장 트리를 말한다.
크루스칼 알고리즘
최소 비용 신장 트리를 만들 수 있는 알고리즘은 대표적으로 크루스칼(Kruskal) 알고리즘이 있다. 크루스칼 알고리즘은 가장 비용이 적은 간선들을 먼저 연결하여 최소 비용 신장 트릴르 만드는 방법이다. (반대로 노드에 가능한 모든 간선을 연결한 후 비용이 가장 큰 간선을 제거하는 방법도 크루스칼 알고리즘이다.) 크루스칼 알고리즘은 매 순간 가장 비용이 적은 간선을 먼저 "고려"한다는 점에서 매 순간 최선의 선택 최적의 해가 되는 그리디에 속하기도 한다. 굳이 "고려"한다고 표현한 이유는 가장 비용이 적은 간선을 반드시 연결하는 것이 아니라, 연결할지 말지 판단한다는 점에서 "고려"한다고 표현했다. 정리하면 다음과 같다.
- (사용한 간선의 수) == (노드의 수 -1) 가 될 때까지 아래의 작업을 반복한다.
- 가장 비용이 작은 간선을 선택한다.
- 이 간선으로 연결될 두 노드가 연결되어 있지 않다면, 두 노드를 연결한다.
n개의 노드를 연결하기 위해서 n-1개의 간선이 반드시 필요하다는 것은 너무 자명한 사실이다. 혹시 잘 이해가 되지 않는다면 직접 종이에 그려보면 직관적으로 이해할 수 있을 것이다.
아래의 예시를 살펴보자.
먼저 비용이 가장 적은 비용이 1인 간선을 살펴보자. 이 간선을 선택하면 노드 4와 3을 연결할 수 있다. 4와 3은 눈으로 봤을 때 아직 연결되어 있지 않다. ( 연결여부를 판단하는 알고리즘은 잠시 후 더 살펴본다.) 그렇기 때문에 크루스칼 알고리즘에 따라서 비용이 1인 간선을 선택하자.
다음으로 비용이 저렴한 비용 2 간선을 살펴보자. 노드 1과 2도 서로 연결되어 있지 않기 때문에 마찬가지로 선택 가능하다.
비용 4인 간선은 노드 2와 노드 3을 연결하고 있다. 눈으로 봤을 때는 쉽게 노드 2와 노드 3은 연결되어 있지 않음을 알 수 있지만 프로그래머스 질문하기 게시판을 살펴보면 이 부분을 고려하지 못해서 잘못된 코드를 작성한 경우가 발견할 수 있다. 주로 "양쪽 노드가 연결된 적이 없다면, 두 노드를 연결한다." 라고 생각했을 경우 이 경우에서 오류가 발생할 것이다.
다음으로 비용이 6인 간선을 살펴보자. 양쪽 노드 4와 2는 이미 연결되어 있었다. 때문에 비용이 6인 간선이 선택되면 신장 트리의 조건을 만족하지 않는다. 비용이 6인 간선은 선택하지 않고 넘어가겠다.
비용이 7인 간선도 마찬가지로 노드 1과 노드 4가 이미 연결되어 있기 때문에 불필요한 연결이다. 비용이 7 인 간선도 선택하지 않고 넘어가자.
마지막으로 비용이 9인 간선은 노드 0과 노드 3을 연결한다. 이 둘은 서로 연결되지 않은 노드이기 때문에 연결해준다.
최종적으로 4개의 간선으로 5개의 노드를 최소 비용 16을 사용하여 연결했다.
노드의 연결 여부 판단
다음으로 살펴볼 부분은 그렇다면 두 노드가 연결되어 있음은 어떻게 알 수 있을까? 여기에는 두 가지 방법이 있다. 하나는 BFS/DFS를 사용하는 방법이고 다른 하나는 Union Find(합집합 찾기)를 사용하는 방법이다. 이번 문제에서 이 둘을 사용할 경우 특징은 다음과 같다. (BFS/DFS 설명은 이 글을 참고, 여기서는 Union Find만 부연 설명을 진행한다.)
BFS/DFS의 특징
- 노드 개수 \(n\)에 대해서 \(O(n)\) 시간 탐색을 보장한다.
- 노드들의 연결 정보를 기록하고 있다.
Union Find의 특징
- 노드 개수 \(n\)에 대해서 \(O(n)\) 시간 탐색을 보장한다.
- 노드의 연결 정보가 아니라 최상단 부모 노드의 정보만 기록하고 있다.
두 방법 모두 연결여부를 판단하기 위해서 최악의 경우 모든 노드를 탐색해야 한다. 그리고, BFS/DFS는 모든 노드를 탐색하기 위해서는 노드들의 연결 정보가 반드시 필요하지만, Union Find는 노드들이 어떻게 연결되어 있는지는 알 수 없다. 오직 최상단 부모 노드의 정보만 필요하다. 즉, 다음과 같은 경우를 살펴보자.
위 그림처럼 모든 노드는 부모 노드의 정보를 가진다. 그리고 부모노드가 자신과 동일하다면 그 노드가 곧 부모 노드이다. 만약 새로운 간선이 노드 1과 노드 3이 연결되어 있음을 확인하고 싶다면, 서로의 부모 노드를 확인하면 된다. 노드 1의 부모노드와 노드 3의 부모 노드는 서로 다르기 때문에 연결되어 있지 않다고 볼 수 있다. 그리고 서로 연결을 한 후에는 부모 노드 정보를 갱신한다.
이때 3의 부모노드 2의 부모노드 정보만 갱신되었음을 유의하자. 노드 3의 부모 노드는 노드 2이고 노드 2의 부모노드는 0으로 변경되었다. 때문에 다음에 다시 노드 3의 부모 노드를 요청하게 되면 재귀적으로 노드 0을 찾을 수 있다. 이때 노드 3의 부모 노드를 갱신하면 된다. 때문에 미리 사용할지 안 할지 모를 모든 노드의 부모 노드를 계속 갱신하는 행위는 불필요하다. 이 부분에 유의해서 코드를 살펴보자.
BFS/DFS vs Union Find성능 비교
주어진 총 간선의 수를 \(E\), 총 노드의 개수를 \(N\) 이라고 했을 때 시간 복잡도는 \(O(E\cdot N)\)으로 동일하다. 하지만 BFS/DFS는 모든 노드의 연결 정보를 가지기 위한 몇 가지 연산들을 더 하기 때문에 약 1.5배 정도 더 오래 걸리는 것을 확인할 수 있었다. 두 방법 시간 복잡도는 \(O(E\cdot N)\)로 비슷하고 모두 허용범위 내에서 연산을 처리하기 때문에 상황에 맞게 사용하면 될 듯하다.
구현
BFS로 구현
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <queue>
using namespace std;
struct Node{
Node(int num) : mNum(num)
{}
vector<Node*> mAdjacent; // 인접 노드들의 정보
int mNum; // 방문 기록 표시를 위한 노드 정보
};
struct Compare{
bool operator() (const vector<int>& left, const vector<int>& right)
{
return left[2] < right[2];
}
};
bool IsConnected(Node* start, Node* target) //BFS로 구현
{
queue<Node*> q;
vector<bool> visited (100,false);
q.push(start);
visited[start->mNum] = true;
while(!q.empty())
{
Node* cur = q.front();
q.pop();
for(Node* ad : cur->mAdjacent)
{
if(ad == target)
return true;
if(visited[ad->mNum] == false)
{
q.push(ad);
visited[ad->mNum] = true;
}
}
}
return false;
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
int numEdges = 0;
vector<Node*> nodes(n);
for(int i= 0; i < n; i++)
{
nodes[i] = new Node(i);
}
sort(costs.begin(), costs.end(), Compare());
int index = 0;
while(numEdges < n-1 && index < costs.size())
{
int a = costs[index][0];
int b = costs[index][1];
// a와 b가 연결되어 있지 않다면...
if(!IsConnected(nodes[a], nodes[b]))
{
nodes[a]->mAdjacent.emplace_back(nodes[b]);
nodes[b]->mAdjacent.emplace_back(nodes[a]);
answer += costs[index][2];
numEdges++;
}
index++;
}
for(int i= 0; i < n; i++)
{
delete nodes[i];
}
return answer;
}Union Find로 구현
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool Compare(const vector<int>& left, const vector<int>& right)
{
return left[2] < right[2];
}
// 최상위 parent 노드를 찾아서 반환
int GetParent(int parent[], int n)
{
// 최상위 parent 인 경우
if(parent[n] == n) return n;
else
{
parent[n] = GetParent(parent, parent[n]);
return parent[n];
}
}
int solution(int n, vector<vector<int>> costs) {
int answer = 0;
int numEdge = 0;
int parent[100] = {};
for(int i = 0; i < 100; i++)
parent[i] = i;
sort(costs.begin(), costs.end(), Compare);
for(int i = 0; i < costs.size(); i++)
{
int a = GetParent(parent, costs[i][0]);
int b = GetParent(parent, costs[i][1]);
// 서로 연결되어 있지 않은 섬이라면
if(a != b)
{
// 최상위 parent 노드 정보만 갱신
parent[b] = parent[a];
numEdge++;
answer += costs[i][2];
if(numEdge == n - 1)
break;
}
}
return answer;
}