[프로그래머스 Level 3] [그리디] 섬 연결하기 (C++)

안녕하세요, 코딩하는 경제학도 쏘코입니다.

정말 오랜만에 푸는 Level3인데, 역시 난이도는 거짓말을 치지 않았습니다.

다 풀어놓고 사소한 부분에서 실수하는 바람에 2시간동안 쩔쩔맸습니다.

바로 풀어보겠습니다.

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/42861

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

4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4

programmers.co.kr

0. 문제 설명

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

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

0.0. 제한사항

섬의 개수 n은 1 이상 100 이하입니다.
costs의 길이는 ((n-1) * n) / 2이하입니다.
임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
연결할 수 없는 섬은 주어지지 않습니다.

0.1. 입출력 예

n	costs	return
4	[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]	4

0.2. 입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

1. 풀이 과정

가장 기본이 되는 크루스칼 알고리즘을 알고 있어야 쉽게 해결이 가능합니다.

~~저는 1시간 고민하다가 도저히 모르겠어서 검색했습니다..~~

크루스칼 알고리즘이란 모든 노드를 최소한의 비용으로 연결하는 알고리즘입니다.

문제와 딱 맞는 알고리즘이죠?

이 알고리즘의 기초는 비용을 기준으로 정렬한 후에 적은 비용인 노드부터 하나씩 추가하는 것입니다. 대신 사이클이 일어나게 되면 그 다리는 버리고 다음 다리로 넘어가야 합니다.

먼저 비용 순서대로 정렬합니다. 정렬을 할 때 비용이 costs 안쪽에 위치한 벡터의 3번째 요소이므로 따로 comp라는 bool함수를 하나 만들어줍니다. 그리고 sort 함수의 세 번째 파라미터로 comp를 넣어주면 됩니다.

그 다음엔 사이클을 방지하기 위해서 부모노드를 나타내는 parent라는 int형 array를 만듭니다.

그리고 index를 그대로 array안에 넣어줍니다.

각 노드가 연결되면 그 노드의 index는 둘 중 낮은 노드로 바뀌게 할 예정입니다.

이제 for문을 돌려서 다리를 연결해줍니다. 이미 비용순서대로 정렬이 되어있기 때문에 순서대로 연결해주면 됩니다.

두 노드가 하나의 다리로 연결되면 두 노드 중 낮은 숫자의 부모노드쪽으로 parent가 변화하게 됩니다.

이 말은 같은 parent[i]를 가졌다면 같은 부모(이미 연결되어있음)라는 이야기이기 때문에 그 다리는 그냥 넘어갑니다.

여기서 주의해야 할 점은 parent를 변경시킬 때 값을 따로 저장하는 것이 필요합니다. 그렇지 않으면 바뀐 parent의 영향을 받아 정상적으로 parent가 변화하지 않을 수 있습니다. (여기서 2시간을 버렸습니다 ㅠ)

부모 노드가 같은 경우가 아니라면 answer에 cost를 추가해줍니다. 그리고 저는 추가로 check 변수를 만들었는데, 만약 0부터 시작하지 않는 노드들을 만나게 되었을 때를 대비했습니다.

모든 노드를 연결하면 다리의 수는 n-1이 되기 때문에, answer에 cost를 추가할 때마다 check를 1씩 늘려서 check가 n-1이 되는 순간 for문을 종료하게 만들었습니다. 여기까지 만드셨다면 깔끔하게 돌아갈 것입니다!

2. 소스 코드

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

using namespace std;

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

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    int check = 0;
    
    // 0. 정렬
    sort(costs.begin(), costs.end(), comp);
    
    // 1. 부모노드 확인하는 int array 만들기
    int parent[n];
    for (int i = 0; i < n; ++i)
        parent[i] = i;
    
    // 2. 다리들을 비용이 적게 드는 순서대로 확인해서 사이클이 안생기는 경우에만 연결
    for(int i = 0; i < costs.size(); ++i){
        if(parent[costs[i][0]] != parent[costs[i][1]]){
            if(parent[costs[i][0]] > parent[costs[i][1]]){
            	int bigtemp = parent[costs[i][0]];
        		int smalltemp = parent[costs[i][1]];
                for(int j = 0; j < n; ++j){
                    if(parent[j] == bigtemp)
                        parent[j] = smalltemp;
                }
            }
            else{
            	int bigtemp = parent[costs[i][1]];
        		int smalltemp = parent[costs[i][0]];
                for(int j = 0; j < n; ++j){
                    if(parent[j] == bigtemp)
                        parent[j] = smalltemp;
                }
            }
            answer += costs[i][2];
            ++check;
        }
        if(check == n-1)
            break;
    }
    
    return answer;
}

3. 후기

level3정도 되니 모르는 알고리즘들이 등장합니다. 알고리즘을 모른다면 아이디어를 떠올리기 굉장히 어려운 문제였습니다.

다만 저처럼 검색을 해서 크루스칼 알고리즘을 알았다고 해도 코딩 과정에서 생기는 사소한 문제..는 각자 해결하셔야 합니다. 저같은 경우 bigtemp와 smalltemp를 이용해서 고통의 2시간 디버깅을 끝마쳤습니다.(보는 것 만으로는 해결할 수 없어 컴파일러의 도움을 받았습니다) 여러분들은 꼭 잘 안돌아가는 것 같으면 본인을 믿지 마시고 컴파일러를 믿으시기 바랍니다 (?)

추가로 크루스칼 알고리즘에 대해서는 따로 게시물을 올려볼까 합니다. 유용하게 써먹을 수 있어 보입니다.

저작자표시

[프로그래머스 Level 3] [그리디] 섬 연결하기 (C++)