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

1. 문제 풀이 아이디어

• 프림 알고리즘을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        List<int[]>[] list = new List[n];
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int[] c : costs) {
            list[c[0]].add(new int[]{c[1], c[2]});
            list[c[1]].add(new int[]{c[0], c[2]});
        }
        boolean[] checked = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        checked[0] = true;
        pq.addAll(list[0]);
        int count = 0;
        while (count < n - 1) {
            int[] cur = pq.poll();
            if (checked[cur[0]]) continue;
            answer += cur[1];
            checked[cur[0]] = true;
            count++;
            for (int[] c : list[cur[0]]) {
                if (checked[c[0]]) continue;
                pq.add(c);
            }
        }
        return answer;
    }
}

3. 정리

• 그래프를 구성하기 위해 각 정점에 연결된 간선 정보를 저장한다.

• checked 배열로 방문 여부를 기록하며, 0번 정점에서 시작해 방문 처리를 한다.

• 우선순위 큐를 사용해 현재 트리에 연결된 간선 중 가장 가중치가 작은 간선을 선택한다.

• 선택된 간선이 연결된 정점이 아직 트리에 포함되지 않았다면:
• 해당 간선의 가중치를 결과 값에 더하고, 해당 정점을 방문 처리한다.
• 새롭게 포함된 정점에 연결된 간선들을 큐에 추가한다.

• 모든 정점이 포함될 때까지 위 과정을 반복한 후 결과 값을 반환한다.