[프로그래머스/Java] 섬 연결하기(Greedy 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 Greedy 파트 문제 중 하나인 '섬 연결하기'를 자바를 이용하여 풀어보았다. 

https://school.programmers.co.kr/learn/courses/30/lessons/42861#

프로그래머스

 

 

 접근 자체는 크게 어렵지 않다. 그냥 cost가 작은 순으로 costs 배열을 정렬해 주고, costs 배열을 순회하면서 아직 이어지지 않은 섬들을 이어주는 cost를 answer에 더해주고 리턴하면 된다. 

 이때, 아직 이어지지 않은 섬은 boolean 2차원 배열인 isLinked를 만들어서 확인해주었다. 다만 처음에는 재귀를 이용하지 않고, 그냥 반복문 안에서 섬이 연결되었는지 확인하고, 지금 연결하고 있는 섬들과 원래 연결되어 있던 섬들 역시 서로 다른 섬에 연결되는 것으로 추가했다. 다리를 여러 번 건너더라도 도달 가능만 하면 연결되었다고 보는 것을 고려해 준 것이다. 다만, 재귀를 사용하지 않으니, 아래 케이스를 해결할 수 없었다. 

n = 5
costs = [[0, 1, 1], [2, 3, 1], [3, 4, 2], [1, 2, 2], [0, 4, 100]]

answer = 6
expected = 106

 마지막에 0과 4가 이미 연결되어 있는지 판단할 때, 연결되어 있지 않다고 판단되는 것이 문제였다. 원인을 파악하기 위해 그림을 그려보았더니 아래와 같았다. 

 하얀 선들이 이미 다 연결된 후, 마지막으로 빨간색 선이 연결 되므로써 모든 섬이 다 연결된다. 하지만, 빨간 다리를 연결할 때, 현재 연결하고 있는 섬들인 1과 2에 직접 인접해 있는 0과 3까지는 서로 연결되어 있는 것으로 판단할 수 있으나, 4까지 연결되어 있는 것으로 판단되지 않아서, 마지막으로 불필요한 0, 4 사이의 다리까지 연결하게 되는 것이다. 

 이를 해결하기 위해 재귀를 사용하여, 얼마나 많은 다리를 건너는지에 관계없이 연결되어 있는 다리들을 모두 표시해 주었다. 

import java.util.*;

class Solution {
    public void make_link(int i, int j, boolean[][] isLinked) {
        isLinked[i][j] = true;
        isLinked[j][i] = true;
        int n = isLinked.length;
        for (int k = 0; k < n; k++) {
            if (isLinked[i][k] && !isLinked[j][k]) {
                make_link(j, k, isLinked);
            } else if (isLinked[j][k] && !isLinked[i][k]) {
                make_link(i, k, isLinked);
            }
        }
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        Arrays.sort(costs, (a, b) -> (a[2] - b[2]));
        if (n == 1) return costs[0][2];
        
        boolean[][] isLinked = new boolean[n][n];
        for (boolean[] b : isLinked) Arrays.fill(b, false);
        
        for (int[] cost : costs) {
            int i = cost[0], j = cost[1];
            if (isLinked[i][j] || i == j) continue;
            
            answer += cost[2];
            make_link(i, j, isLinked);
        }
        
        return answer;
    }
}