[프로그래머스] 섬 연결하기 - Java

풀이 과정

• 프림 알고리즘을 떠올리면 풀이를 쉽게 진행할 수 있다.
• 섬의 갯수가 1 이상, 100 이하로 주어졌으며 절대로 연결될 수 없는 섬은 주어지지 않는다고 하였으므로 시작지점을 임의로 0번 섬으로 지정하여도 아무런 문제가 없다.

기본적인 풀이의 진행방식은 아래와 같다.

1. Edge의 cost에 대해 오름차순 정렬하는 Priority Queue를 준비한다.
2. 현재까지 방문한 각 섬에 대하여 이하의 과정을 수행한다.
   • 전체 edge에서 현재 선택중인 섬과 연결된 edge를 찾는다.
   • 해당 edge의 다른 한 쪽 끝이 아직까지 방문하지 않은 섬과 연결되어있는지를 확인한다.
   • 방문하지 않은 섬과 연결되어 있는 edge는 다음번에 설치될 다리가 될 가능성이 있으므로 1에서 준비한 Priority Queue에 추가한다.
3. 위 2의 과정이 끝나면 1에서 준비한 Priority Queue에서 minimum cost edge를 poll한다.
   • 남은 edge 리스트에서 이번에 선택된 minimum cost edge를 제거한다.
   • 지금까지 방문한 섬 목록에 선택된 edge의 양 끝 섬을 추가한다. (둘 중 하나는 아직 방문되지 않은 상태였다.)
   • 전체 비용에 선택된 edge의 cost를 추가한다.
4. 1~3번의 과정을 방문한 섬의 갯수가 전체 갯수가 될 때 까지 반복한다.

Code

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int totalCost = 0;

        List<Edge> edges = new LinkedList<>();
        for (int[] cost : costs) {
            edges.add(new Edge(cost[0], cost[1], cost[2]));
        }

        Set<Integer> visited = new HashSet<>();
        visited.add(0); // starting point

        while (visited.size() < n) {
            PriorityQueue<Edge> possibleEdges = new PriorityQueue<>();
            for (int island : visited) {
                for (Edge edge : edges) {
                    if (edge.isConnecting(island)
                            && (!visited.contains(edge.getIsland1()) || !visited.contains(edge.getIsland2()))
                    ) {
                        possibleEdges.offer(edge);
                    }
                }
            }

            Edge chosen = possibleEdges.poll();
            edges.remove(chosen);

            visited.add(chosen.getIsland1());
            visited.add(chosen.getIsland2());
            totalCost += chosen.getCost();
        }

        return totalCost;
    }
}

class Edge implements Comparable<Edge> {
    private final int island1;
    private final int island2;
    private final int cost;

    Edge(int island1, int island2, int cost) {
        this.island1 = island1;
        this.island2 = island2;
        this.cost = cost;
    }

    public int getIsland1() {
        return island1;
    }

    public int getIsland2() {
        return island2;
    }

    public boolean isConnecting(int vertex) {
        return vertex == island1 || vertex == island2;
    }

    public int getCost() {
        return cost;
    }

    @Override
    public int compareTo(Edge o) {
        return this.cost - o.getCost();
    }

    public boolean equals(Edge o) {
        return (island1 == o.getIsland1()) && (island2 == o.getIsland2()) && (cost == o.getCost());
    }
}

결과