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

https://school.programmers.co.kr/learn/courses/30/lessons/42861?language=cpp

프로그래머스

그리디

N개의 섬과 그 섬을 잇는 다리 건설 정보가 2차원 배열로 주어진다.

costs배열은 (출발점, 도착점, 비용)을 원소로 갖는 배열임

이때, 모든 섬이 서로 연결되도록 다리를 설치하는 데 드는 최소비용을 반환하는 문제

 

접근방법

처음에는 DFS로 풀어보려고 했다가 안돼서 그리디 문제 답게 그리디하게 풀었다 (?)

목적은 1) 새로운 섬을, 2) 적은 비용으로 가는 것.

그래서 이미 방문한 섬으로부터 갈 수 있는 섬들 중, 가장 비용이 적은 다리를 먼저 pick하는 식으로 풀었다.

음..우선순위 큐를 쓰면 좋을 것 같긴 했지만, 그냥 내가 최소 다리를 구하는 식으로 풀었다.

 

1. 인접행렬 셋팅

각 섬을 출발점으로 하는 모든 다리 정보를 정리한다. ex. 0 : (1(도착점), 1(비용)) ... 이런식으로

2. 그리고 우선 0번 섬을 방문한다고 가정하고 방문한 섬을 담아두는 배열(visitedIslands)에 넣고, 방문했다고 표시한다(visit)

3. 이제 반복문을 도는데, 모든 섬을 방문할 때까지 반복한다. (visitedIslands에 모든 섬이 담길 때 까지) - (못가는 섬은 없다했으니까..)

3.1. 반복문 안에서는, 이미 방문한 섬들로부터 만들 수 있는 다리 중 가장 비용이 싸면서, 아직 방문하지 않은 섬에 도착하는 다리를 고른다. 

4. 반복문이 끝난 후 찾은 다리를 만든다. = 해당 다리로 갈 수 있는 섬을 방문한다. + 비용에 그 다리를 건설하는 비용을 더한다.

 

오답노트

놀랍게도 adj 셋팅할 때 costs.size()가 아니라 n으로 둬서 틀렸었음 레전드..

 

인접행렬에 다리 양방향을 모두 넣어둬서 좀 비효율적이긴 한데 (그래도 크루스칼보다 시간 더 적던데요)

 

근데 크루스칼로 푸는게 너무 로직이 깔끔해 보여서 그걸로도 풀어봅시다.

 

소스코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;


int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    vector<int> visitedIslands;
    vector<bool> visit(n, false);
    
    // adj 셋팅
    int maxCost = 0;
    vector<vector<pair<int,int>>> adj(n);
    for(int i = 0 ; i < costs.size() ; i++){
        adj[costs[i][0]].push_back({costs[i][1], costs[i][2]});
        adj[costs[i][1]].push_back({costs[i][0], costs[i][2]});
        if(maxCost < costs[i][2])
            maxCost = costs[i][2];
    }
    
    // 0번 섬 담기
    visitedIslands.push_back(0);
    visit[0] = true;
    
    while(visitedIslands.size() < n) {
        int min = maxCost;
        int minIsland = 0;
        
        for(int i = 0 ; i < visitedIslands.size() ; i++){
            // 섬 하나에 대해서 연결되는 섬 확인
            int now = visitedIslands[i];
            for(int j = 0 ; j < adj[now].size() ; j++){
                if(!visit[adj[now][j].first] && min >= adj[now][j].second){
                    min = adj[now][j].second;
                    minIsland = adj[now][j].first;
                }
            }
        }
        // 최소 거리 섬 방문
        visit[minIsland] = true;
        visitedIslands.push_back(minIsland);
        answer += min;
    }
    
    return answer;
}

 

크루스칼 풀이

각 섬의 연결정보를 저장하기 위해, 부모자식 관계를 이용하는 알고리즘이다.

모든 섬에 대해서 우선 본인의 부모노드는 본인이라고 초기화해두고, 섬을 다리로 연결할 때마다

출발점을 도착점의 부모노드로 설정해두면, 다리를 탐색할 때 두 섬이 이미 연결되어 있는지 아닌지 빠르게 확인할 수 있다.

그 전에, 최소비용을 구하는 것을 보장하기 위해서 costs배열을 cost에 대해 오름차순으로 정렬해둔다.

그리고나서 가장 적은 비용이 드는 다리부터 확인하면서 아직 연결되지 않는 섬들을 연결해가면

최소비용을 만족시키면서 모든 섬을 연결할 수 있다.

 

1. (costs배열 정렬 후) 첫번째 다리 정보부터 보면서, 출발점과 도착점 각각의 부모 노드를 찾는다.

2. 두 섬의 부모노드가 다르면, 이 두 섬은 아직 연결되지 않았다는 뜻이므로 (이전 풀이와 연결해 설명하면, 두 점 중 하나는 아직 방문하지 않은 섬이므로), 다리를 건설한다. = 도착점의 부모노드에 출발점(의 부모노드)를 넣고, 결과값에 해당 다리 비용을 더한다.

2-1. 두 섬의 부모노드가 같으면 이미 연결되어있는 섬이므로 패스

이렇게 반복문이 끝나면 결과값이 최소비용이 된다. 끝~

 

 

소스코드

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

using namespace std;

int parents[100];

int getParents(int node){
    if(parents[node] == node){
        return node;
    } else {
        return parents[node] = getParents(parents[node]);
    }
}

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

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    for(int i = 0 ; i < n ; i++){
        parents[i] = i;
    }
    
    sort(costs.begin(), costs.end(), compare);
    
    for(int i = 0 ; i < costs.size(); i++){
        int start = getParents(costs[i][0]);
        int end = getParents(costs[i][1]);
        int cost = costs[i][2];
        
        if(start != end){
            parents[end] = start;
            answer += cost;
        }
    }
    
    return answer;
}