[랜덤 마라톤] Model Railroad(13151)

1. 문제 풀이 아이디어

• 최소 신장 트리(MST) 알고리즘을 사용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        int l = Integer.parseInt(stringTokenizer.nextToken());

        List<Map<Integer, Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new HashMap<>());
        }
        int totalLength = 0;
        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(stringTokenizer.nextToken()) - 1;
            int b = Integer.parseInt(stringTokenizer.nextToken()) - 1;
            int c = Integer.parseInt(stringTokenizer.nextToken());
            if (i < l)
                totalLength += c;
            int min = Math.min(c, list.get(a).getOrDefault(b, Integer.MAX_VALUE));
            list.get(a).put(b, min);
            list.get(b).put(a, min);
        }
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        pq.add(new AbstractMap.SimpleEntry<>(0, 0));

        boolean[] chk = new boolean[n];
        int count = 0;
        int sum = 0;
        while (!pq.isEmpty() && count < n) {
            Map.Entry<Integer, Integer> cur = pq.poll();
            if (chk[cur.getKey()]) continue;
            chk[cur.getKey()] = true;
            count++;
            sum += cur.getValue();

            for (Map.Entry<Integer, Integer> entry : list.get(cur.getKey()).entrySet()) {
                if (chk[entry.getKey()])
                    continue;
                pq.add(new AbstractMap.SimpleEntry<>(entry.getKey(), entry.getValue()));
            }
        }

        if (sum <= totalLength && count == n) {
            System.out.println("possible");
        } else {
            System.out.println("impossible");
        }
        bufferedReader.close();
    }
}

3. 정리

• a역과 b역 간의 연결 비용을 List<Map<Integer, Integer>> list에 저장하고, 입력 시마다 최소 길이로 갱신한다.

• 기존에 존재하는 철도의 총 길이를 totalLength로 저장한다.

• PriorityQueue를 사용하여 현재 선택할 수 있는 최소 비용의 연결을 계속해서 선택한다.

• new AbstractMap.SimpleEntry<>(0, 0)을 사용하여 0번 역부터 시작한다.

• while문을 돌며 모든 역을 연결하거나, 모든 연결을 확인하면 종료된다.

• pq에서 꺼낸 역이 이미 연결된 역이라면 넘어가고, 그렇지 않으면 그 역에서 연결 가능한 모든 레일을 다시 pq에 추가한다.

• 이 과정을 반복하여 연결된 총 비용이 totalLength 이하이고, 모든 역이 연결되면 "possible", 그렇지 않으면 "impossible"을 출력한다.