프로그래머스 섬 연결하기

- 문제 설명

 

n개의 섬 사이에 다리를 건설하는 비용이 주어질 때 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 하는 solution 작성

 

 

- 입력

 

1) 섬의 개수 n (1 <= N <= 100)

2) costs 의 길이 ((n-1) * n) / 2

3) costs[i][0], costs[i][1] : 연결되는 두 섬의 번호, costs[i][2] : 다리 건설 비용

 

 

- 출력

 

가장 적은 비용으로 모두를 통행할 수 있도록 만드는 최소 비용

 

 

* 문제 풀이의 핵심

 

이 문제를 해결하기 위해 필요한 것은 Kruskal, Union-Find 알고리즘 두 가지 입니다. (이해하는데 참고한 사이트는 하단에 링크 표시하였습니다.)

 

1) Kruskal 알고리즘 : 탐욕법을 통한 최소 간선 거리 찾기

 

2) Union-Find 알고리즘 : 그래프의 사이클 여부 검사

 

 

1. Kruskal 알고리즘

 

Kruskal 알고리즘은 탐욕법을 사용해 그래프의 모든 정점을 최소 가중치를 가진 간선으로 연결하는 것 입니다. 순서는 다음과 같습니다.

 

1) 가중치를 기준으로 간선 정렬 (오름차순)

 

2) 노드를 간선으로 연결

 

2-1) 노드와 노드를 간선으로 연결 했을 때 사이클(순환)이 발생하는지 검사

 

[같은 집합에 속하는지 검사, Union-Find 알고리즘 활용]

 

2-2) 사이클 발생시, 해당 간선 제거 혹은 무시

 

2-3) 사이클이 발생하지 않을 시, 가중치의 크기가 작은 순으로 노드를 연결

 

3) 최소 가중치를 가진 비 순환 그래프 완성

 

 

예제) 1) ~ 3) 순서를 통한 동작 원리

 

 

Kruskal 알고리즘 순서

 

 

Kruskal 알고리즘은 탐욕적인 방법으로 항상 최적의 답을 도출하기 때문에 그래프를 형성하면서 얻는 가중치의 크기를 모두 더하면 정답이 됩니다. (사이클 간선 제외)

 

 

2. Union-Find 알고리즘

 

그래프가 사이클을 형성하는지 여부를 알기 위해서는 Union-Find 알고리즘을 이해해야 합니다.

 

이 알고리즘은 서로 중복되지 않는 집합을 찾는 것 입니다.

 

서로 같은 집합인지 아닌지를 알게 되면 그래프가 사이클(순환)인지 아닌지 알 수 있기 때문입니다.

 

그 이유는 다음과 같습니다.

 

1) 집합이 겹치는 경우

 

위의 그림 i = 4 에서, 간선 {0, 1, 2, 3} 은 집합을 이루고 있습니다. 그 상태에서 간선 {1, 2} 를 연결하려고 하면 1 과 2 는 모두 {0, 1, 2, 3} 이라는 같은 집합에 속하기 때문에 사이클이 형성 됩니다.

 

2) 집합이 겹치지 않는 경우

 

위의 그림 i = 2 에서, {0, 1, 3} 은 집합을 이루고 있습니다. 그 상태에서 간선 {0, 2} 를 연결하려고 하면 0 은 {0, 1, 3} 집합에 속하고 2 는 어디에도 속하지 않기 때문에 같은 집합에 속하지 않고 서로 연결해도 사이클이 형성되지 않습니다.

 

 

- 배열을 사용한 Union-Find 구현

 

트리 구조의 루트 노드를 저장할 배열을 선언하고, 3가지 함수를 구현할 수 있어야 합니다.

 

1) void make_set(int n) : 노드의 수 만큼 배열을 초기화 합니다. (현재 인덱스 = 루트)

 

2) int _find(int x) : x 인덱스의 루트 노드를 찾습니다, 트리 구조이므로 (현재 인덱스 == 루트) 인 최상위 노드를 찾는 함수를 구현합니다. (최적화 : 최상위 노드를 찾으면 하위 노드의 루트 값을 갱신합니다.)

 

- 최적화 하지 않은 코드

 

int _find(int x) {
	if (root[x] != x) {
		return _find(root[x]);
	}
	else {
		return root[x];
	}
}

 

 

- 최적화 한 코드

 

int _find(int x) {
	if (root[x] != x) {
		return root[x] = _find(root[x]);
	}
	else {
		return root[x];
	}
}

 

 

3) void _union(int s, int e) : end 노드가 start 노드 루트 값으로 가지게 함으로서 트리구조의 집합을 형성합니다.

 

 

예제) 1) ~ 3) 함수를 사용한 동작 원리

 

 

Union-Find 알고리즘 순서

 

 

- 소스코드

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int root[101];

// 루트 초기화
void make_set(int n) {
	int i;
	for (i = 0; i < n; i++) {
		root[i] = i;
	}
}

// 각 집합의 루트 노드 찾기
int _find(int x) {
	if (root[x] != x) {
		return root[x] = _find(root[x]);
	}
	else {
		return root[x];
	}
}

// 집합 형성
void _union(int _x, int _y) {
	int x = _find(_x);
	int y = _find(_y);

	root[y] = x;
}

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

int solution(int n, vector<vector<int>> costs) {
	int answer = 0;

	make_set(n);

	// 1. 간선 가중치 오름차순 정렬
	sort(costs.begin(), costs.end(), cmp);

	// 2. 간선 선택
	int i;
	for (i = 0; i < costs.size(); i++) {
		// 사이클 형성 체크 (같은 집합인지 체크)
		int s = costs[i][0];
		int e = costs[i][1];

		// 사이클이 형성되지 않는 경우 간선 연결 및 집합 형성
		if (_find(s) != _find(e)) {
			// 집합 형성
			_union(s, e);

			// 간선 연결
			answer += costs[i][2];
		}
	}

	return answer;
}

 

 

- 문제링크 : programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요

 

 

- 참고

1) gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

2) gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html