[Algo Rhythm🕺💃] 프로그래머스 고득점 kit 섬 연결하기

📚 문제 설명

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

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

 

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.

• costs의 길이는 ((n-1) * n) / 2이하입니다.

• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.

• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.

• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.

• 연결할 수 없는 섬은 주어지지 않습니다.

🎯 어떻게 풀었나

첫번째 시도 (20점 / 100점)

import java.util.Arrays;

class Solution {
    public int solution(int n, int[][] costs) {
        int minCost = 0;
        int nReachable = 0;
        boolean[] reachableStatus = new boolean[n]; // default : false
        
        Arrays.sort(costs, (c1, c2) -> Integer.compare(c1[2], c2[2]));
        
        for(int i = 0; i < costs.length; i++) {
            if(nReachable == n) break;
            
            int island1 = costs[i][0];
            int island2 = costs[i][1];
            int cost = costs[i][2];
            
            if(!reachableStatus[island1] && !reachableStatus[island2]) { // island1과 island2 모두 도달할 수 없는 상태
                minCost += cost;
                reachableStatus[island1] = true;
                reachableStatus[island2] = true;
                nReachable += 2;
            }
            
            if(!reachableStatus[island1]) { //island1이 도달할 수 없는 상태
                minCost += cost;
                reachableStatus[island1] = true;
                nReachable++;
            }
            
            if(!reachableStatus[island2]) { //island2가 도달할 수 없는 상태
                minCost += cost;
                reachableStatus[island2] = true;
                nReachable++;
            }                               
        }
        
        return minCost;
    }
}

 

두번째 시도 (32.5점 / 100점)

import java.util.Arrays;

class Solution {
    public int solution(int n, int[][] costs) {
        int minCost = 0;
        int nSeparated = n;
        boolean[] reachableStatus = new boolean[n]; // default : false
        
        // cost를 기준으로 오름차순 정렬
        Arrays.sort(costs, (c1, c2) -> Integer.compare(c1[2], c2[2]));
        
      
        
        for(int i = 0; i < costs.length; i++) {
            if(nSeparated == 1) break; // 모든 섬이 하나가 되면 탈출
            
            int island1 = costs[i][0];
            int island2 = costs[i][1];
            int cost = costs[i][2];
           
            
            if(reachableStatus[island1] && reachableStatus[island2] && nSeparated > 1) { // 두 섬 모두 도달할 수 있는데 여전히 분리되어 있을 때 
                minCost += cost;
                nSeparated--;
                continue;
            } 
            
            if(!reachableStatus[island1] && !reachableStatus[island2]) { // 두 섬 모두 도달할 수 없는 상태
                minCost += cost;
                reachableStatus[island1] = true;
                reachableStatus[island2] = true;
                nSeparated--;
                continue;
            }
            
            if(!reachableStatus[island1]) { //island1이 도달할 수 없는 상태
                minCost += cost;
                reachableStatus[island1] = true;
                nSeparated--;
                continue;
            }
            
            if(!reachableStatus[island2]) { //island2가 도달할 수 없는 상태
                minCost += cost;
                reachableStatus[island2] = true;
                nSeparated--;
                continue;
            }            
        }
        
        return minCost;
    }
}

 

최종 코드

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        HashMap<Integer, Integer> graph = new HashMap<>();
        
        // init graph
        for(int i = 0;i < n; i++) graph.put(i, i);
        
        // cost를 기준으로 오름차순 정렬
        Arrays.sort(costs, (o1, o2) -> Integer.compare(o1[2], o2[2]));
        
        for(int i = 0; i < costs.length; i++) {
            int start = getparent(graph, costs[i][0]);
            int end = getparent(graph, costs[i][1]);
            
            if(start != end) {
                answer += costs[i][2];
                graph.put(start, end);
            }
        }
        
        return answer;
    }
    
    public int getparent(HashMap<Integer, Integer> graph, int child) {
        if(graph.get(child) != child) {
            return getparent(graph, graph.get(child));    
        }
        
        return child;
    }
}

 

🧐 왜 저렇게 풀었나

첫번째 시도 (20점/ 100점)

알고리즘 시간에 교수님께서 그리디 알고리즘을 가르쳐 주시며 강조하신 말씀이 있다.

 

"그리디 알고리즘의 본질은 현재 시점에서의 최선의 선택을 하는 것이다."

 

그리디 알고리즘 문제들을 풀면서 교수님의 말씀을 되뇌이다보니 그리디 알고리즘 접근 방법을 깨달았다.

먼저 시점이나 단계라고 부를 수 있는 무언가가 있는가를 따져봐야 한다. 문제에서 주어지지 않았다면 그것을 발견해야 한다.

다음으로는 무엇이 최선의 선택인지 발견해야 한다.

 

문제를 읽어보니 문제 자체에서는 시점이나 단계라고 부를만한 것을 찾을 수 없었다. 그래서 생각해보니 문제에서 요구하는 것이 섬을 모두 연결하기 위해 드는 최소한의 다리 건설 비용이기 때문에 가장 작은 비용부터 확인하면 될 것 같았다.

 

다음으로 최선의 선택이 무엇인가를 생각했는데 모든 섬을 도달할 때까지 비용을 더해주면 될 것 같았다.

 

하지만 이 알고리즘으로는 아래와 같이 섬이 두 그룹으로 나뉘는 경우 동그라미로 표시한 부분을 확인하지 않기 때문에 수정이 필요했다.

 

두번째 시도 (32.5점/ 100점)

앞서 언급한 문제를 해결하기 위해 고민하던 중 '두 섬이 연결되었다면 하나의 섬으로 취급하면 되지 않나?' 라는 생각을 했다. 그래서 분리된 섬의 개수를 변수로 두고 그것이 1이 될 때까지 비용 더하기를 반복하도록 코드를 작성했다.

 

하지만 아래와 같이 불필요한 비용까지 더해버리는 문제가 있었다.

 

최종 코드

한 섬이 다른 어떤 섬과 이어지는지 그래프로 표현할 필요가 있었다.

그래서 해시맵을 통해 섬이 연결되는 것을 그래프로 표현했다.

그리고나서 한 섬과 다른 섬의 최종 목적지가 같은 경우(= 또 다른 섬을 통해 서로 오고 갈 수 있는 상황)를 제외하고는 비용을 더하도록 코드를 작성했다.

 

📖 무엇을 배웠나

해시맵을 통해 그래프를 표현하는 방법을 배웠다. 앞으로 유용하게 쓰일 것 같다!

https://stackoverflow.com/questions/34664134/implementing-a-graph-using-a-hashmap

Implementing a Graph using a HashMap