[Level 3] 섬 연결하기

[Level 3] 섬 연결하기

반응형

각 노드를 최소 비용으로 연결시키는 문제이다. 최소 신장 트리를 만드는 Kruskal 알고리즘을 사용하면 된다. 알고리즘은 간단하다. 우선 cost를 기준으로 오름차순 정렬시킨다.

i번 째 cost를 골라 두 섬이 연결되어 있는지 확인한다. 만약 연결되어 있다면(같은 그룹이라면) 다시 연결할 필요없다. 만약 연결되어 있지 않다면 (같은 그룹이 아니라면) 두 노드를 연결시키고(같은 그룹으로 표시) 해당 비용을 누적시킨다.

이를 모든 costs 요소에 대해 확인하면 된다.

여기서 핵심은 두 섬이 서로 연결되어 있는지, 같은 그룹에 있는지 확인하는 방법이다. 방법은 생각보다 간단한다. 우선 섬의 개수인 n의 크기를 가지는 int 타입 원소를 저장하는 1차원 배열을 하나 생성한다. 초기값은 모두 -1로 설정한다.

배열의 이름은 groupIDs이다. groupIDs[i]는 섬 i가 속한 그룹의 값이다. groupIDs[0] == groupIDs[2]이면 섬 0과 2는 서로 같은 그룹에 속해있는 것이다. 즉 연결되어 있다고 본다. 값 설정의 기준은 상관없다.

만약 현재 cost가 2이고 두 노드(섬)가 0, 2라면 두 노드의 그룹ID를 확인한다. 만약 두 값이 모두 -1이라면, 어디에도 연결되어 있지 않으므로 두 노드를 하나의 그룹으로 만든다. 여기서 그룹ID는 두 노드의 ID(0, 2)중 더 작은 값으로 설정한다. 즉 groupIDs[0] == groupIDs[2] == 0이 된다.

또 다른 경우로 하나의 노드는 그룹에 속해있고 하나의 노드는 그룹이 없을 수 있다. 그럼 그룹이 없는 노드를 다른 노드의 그룹으로 포함시킨다. 만약 노드 2와 3에 대해 groupIDs[2] == 0이고 groupIDs[3] == -1일 경우 groupIDs[3] = 0으로 만들어주면 된다.

또 다른 경우로 두 노드 모두 그룹이 있는 경우이다. 여기는 두 가지로 나뉜다. 같은 그룹에 속해 있거나 다른 그룹에 속해있거나.

같은 그룹에 속해 있다면 굳이 연결할 필요가 없으므로 스킵한다. 같은 그룹이 아니라면 두 그룹을 합쳐야 한다.(연결시켜야 한다.) 만약 groupIDs[3] == 0이고 groupIDs[6] == 6이라면, 노드 6을 노드 3 그룹에 포함시키던가, 그 반대로 해야한다. 아무거나 상관은 없지만 여기선 더 작은 그룹ID로 이동시킨다. 단순히 노드 6의 그룹ID만 변경하면 안되고, groupIDs를 돌면서 값이 6인 노드를 모두 0으로 변경해주어야 한다.

이를 반복할 때마다 cost를 누적시켜주면 정답이 된다.

#include #include #include using namespace std; int solution(int n, vector> costs) { // cost 기준 오름차순 정렬 sort(costs.begin(), costs.end(), [](const vector& v1, const vector& v2) { return v1[2] < v2[2]; }); // groupIDs[i] => 섬 i가 속해있는 그룹ID vector groupIDs(n, -1); int minCost = 0; for(int i = 0; i < costs.size(); ++i) { int id1 = costs[i][0]; int id2 = costs[i][1]; int cost = costs[i][2]; // 두 노드가 아직 어떤 그룹에도 속해있지 않다면 if(groupIDs[id1] == -1 && groupIDs[id2] == -1) { // 두 노드의 그룹 ID를 둘 중 더 작은 id로 설정 int newGroupID = min(id1, id2); groupIDs[id1] = newGroupID; groupIDs[id2] = newGroupID; } else if(groupIDs[id1] == -1 || groupIDs[id2] == -1) { // 두 노드 중 하나만 그룹에 속해 있는 경우 // 그룹에 속해 있지 않은 섬의 그룹ID를 // 다른 노드가 속해 있는 그룹ID로 설정 if(groupIDs[id1] == -1) groupIDs[id1] = groupIDs[id2]; else groupIDs[id2] = groupIDs[id1]; } else // 두 노드 모두 (서로 다른) 그룹에 속해 있는 경우 { // 두 노드가 같은 그룹이면 연결하지 않음 if(groupIDs[id1] == groupIDs[id2]) continue; // groupIDs(id1) 과 groupIDs(id2) 중 더 작은 값으로 통일 // ex) groupIDs(id1): 3, groupIDs(id2): 5라면 // groupIDs(x) = 5인 모든 값을 3으로 변경 int maxGroupID = max(groupIDs[id1], groupIDs[id2]); int minGroupID = min(groupIDs[id1], groupIDs[id2]); for(int i = 0; i < groupIDs.size(); ++i) { if(groupIDs[i] == maxGroupID) groupIDs[i] = minGroupID; } } // cost 추가 minCost += cost; } return minCost; }

from http://woo-dev.tistory.com/295 by ccl(A) rewrite - 2021-09-21 16:26:41