섬 연결하기 (프로그래머스)

간단하게 풀어봤지만 역시 예상대로 대다수 케이스가 실패로 떴다. 

 

푼 방법은 비용 순서로 오름차순 정렬하여, 순서대로 다리를 설치하면서 방문하는 섬을 기록해 놓는다. 다리를 설치할 위치의 두 섬이 이미 모두 다리가 있는 경우에는 설치하지 않는다. 그렇게 모든 섬을 방문할 때까지 반복한다. 

 

하지만 이 방법이 잘못된 이유는 다음 같은 케이스 때문이다. 

 

다음과 같이 5개의 섬이 있고 [[0,1,1],[0,2,2],[1,2,5],[2,3,8],[3,4,1]] 인 경우를 생각해보자.

 

우선 비용으로 오름차순을 하면 [[0,1,1],[3,4,1],[0,2,2],[1,2,5],[2,3,8]]이 된다. 내가 했던 방식으로 순서대로 3번째까지 다리를 이어보면 다음과 같이 된다.

 

이렇게 모든 섬을 방문했다고 판단하고 다리 설치를 종료한다. 하지만 모든 섬이 이어져 있지 않기 때문에 오답이 된다. 실제로는 이 과정에서 [1,2,5] 다리를 설치를 건너뛰고 [2,3,8]을 설치해야 한다. 

 

이 문제는 어떻게 접근해야 할지를 몰라 결국 풀이를 검색해보게 되었다. 그 결과 MST(최소 신장 트리)와 커 크리스컬 알고리즘을 이용해 푸는 문제였다. 크리스컬 알고리즘에 대한 자세한 내용은 다음 링크를 참조하도록 한다.

크러스컬 알고리즘 (Kruskal Algorithm)

다리가 사이클 형성을 하게되면 낭비되는 다리를 설치하게 되는 경우이므로 최소 비용으로 모든 섬을 다리로 잇기 위해서는 사이클을 제거해야 한다. 이 제거 작업을 위해 벡터 컨테이너 하나를 만들고 다음과 같이 초기화한다. 각 인덱스는 섬에 대한 정보를 뜻한다. 이 컨테이너에는 다리를 설치할 때마다 각 섬의 최상위 부모 섬을 담게 된다.

 

이제 비용 순서대로 다리를 설치해 보도록 하자. 먼저 [0,1,1]을 설치한다. 섬 0과 1을 잇는 다리를 설치하게 되므로, v[0]과 v[1]을 찾는다. 그리고 그 값들 중 더 큰 값에 현재 작은 값의 섬 0을 기록한다. 이는 곧 1번째 섬의 부모 섬이 0이 된다는 뜻이다. 

 

이제 [3,4,1]을 설치한다. 위와 동일한 작업을 하며 그림과 같이 된다.

 

다음으로 [0,2,2]를 설치한다. 섬 2와 0이 이어지므로 다음과 같이 된다.

 

이제 [1,2,5]를 설치한다. 여기서 문제가 생긴다. 이 다리를 설치하면 다음처럼 사이클이 생기게 된다. 

 

이를 판별하는 방법은 다음과 같다. v로 부터 섬 2의 최상위 부모 섬을 찾는다. 최상위 부모 섬은 0이다. 섬 1의 최상위 부모 섬 역시 0이다. 이 둘은 모두 최상위 부모 섬으로 0을 가지므로 다리를 잇는다면 사이클이 생기게 된다. 이러한 이유로 컨테이너 v가 필요하다.

 

이제 마지막 [2,3,8]을 설치한다. 섬 3은 섬 2와 이어진다. 섬 2의 최상위 부모 섬은 0이므로 섬 3의 최상위 부모 섬은 0이 된다. 그리고 자동적으로 섬 4의 최상위 부모 섬도 0이 된다.

 

 

너비 탐색으로 반복문을 빠져나올 조건을 정해보려는 생각도 했지만 할 필요가 없었다. 왜냐하면 v를 이용해 사이클이 생기는 경우는 모조리 배제하기 때문이다.  

 

코드는 다음과 같다.

#include <vector>
#include <algorithm>
using namespace std;

// 최상위 부모 섬을 담을 값
vector<int> parent(101);

bool cmp(const vector<int>& a, const vector<int>& b)
{
	return a[2] < b[2];
}

int find(int x)
{
    // 최상위 부모 섬을 찾을 때 까지 재귀적으로 나아간다.
	if (x == parent[x]) return x;
	else return parent[x] = find(parent[x]);
}

int merge(int a, int b)
{
    // 두 섬의 최상위 부모 섬을 찾는다.
	a = find(a);
	b = find(b);

	// 최상위 부모와 서로 같으면 사이클이므로 다리를 설치하지 않는다.
	if (a == b) return false;
	else
	{
        // 최상위 부모 섬을 컨테이너에 기록해 놓는다.
		if (a > b) parent[a] = b;
		else parent[b] = a;
	}
	return true;
}

int solution(int n, vector<vector<int>> costs)
{
	int answer = 0;
	for (int i = 0; i < n; ++i) parent[i] = i;
    // 비용 오름차순으로 정렬
	sort(costs.begin(), costs.end(), cmp);
	for (int i = 0, size = costs.size(); i < size; ++i)
        // 다리를 잇는 작업
        // 만약 false라면 사이클이 생기는 경우로 다리를 설치하지 않는다.
		if (merge(costs[i][0], costs[i][1]) == true) answer += costs[i][2];

	return answer;
}