[Baekjoon] 백준 11085번: 군사 이동 (JAVA)

문제 11085

11085번: 군사 이동

[ 풀이 과정 ]

입력으로 받는 c와 v를 연결하는데, 가장 넓은 너비를 가지는 간선으로만 연결하는 문제입니다. 시작과 끝이 각각 c와 v이므로 이 점을 유의하며 크루스칼 알고리즘으로 해결할 수 있습니다.

간선을 나타내는 Edge 클래스를 만들고, Comparable을 이용하여 간선의 너비가 넓은 순(내림차순)으로 정렬할 수 있도록 compareTo()를 오버라이딩 합니다.

PriorityQueue를 사용하여 w개의 간선을 저장한 후, makeSet()을 이용하여 자기 자신을 부모로 먼저 설정하여 초기화해줍니다. union()을 통해 c, v가 연결될 때까지 가장 넓은 길부터 차례대로 연결해주면 됩니다. c, v가 연결되는 것은 c의 부모와 v의 부모가 같다는 것을 의미합니다.

union()에서 연결하려는 두 정점을 매개변수로 입력받아, 끝 정점의 부모를 시작정점의 부모로 저장해줌으로써 두 정점을 연결합니다.

c와 v의 부모가 같다면 두 정점이 하나의 경로 안에 연결되었다는 것을 의미하므로 그 때의 너비를 출력하면 우선순위큐에 저장한 것에 따라 가장 작은 너비를 출력하게 됩니다.

[ 코드 ]

import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private static class Edge implements Comparable<Edge> {
        int start, end, width;
        public Edge(int start, int end, int width) {
            this.start = start;
            this.end = end;
            this.width = width;
        }

        @Override
        public int compareTo(Edge e) {
            return e.width - this.width; // 내림차순 정렬
        }
    }

    private static int p, w;
    private static PriorityQueue<Edge> path = new PriorityQueue<>();
    private static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        p = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        parents = new int[p];

        for (int i = 0; i < w; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int width = Integer.parseInt(st.nextToken());
            path.offer(new Edge(start, end, width));
        }

        makeSet();

        while (!path.isEmpty()) {
            Edge e = path.poll();
            union(e.start, e. end);
            if (isCommonParent(c, v)) { // 경로를 모두 연결했다면
                bw.write(String.valueOf(e.width));
                bw.newLine();
                break;
            }
        }

        bw.flush();
    }

    private static void makeSet() {
        for (int i = 0; i < p; i++) {
            parents[i] = i;
        }
    }

    private static void union(int x, int y) {
        x = findParent(x);
        y = findParent(y);
        parents[y] = x;
    }

    private static int findParent(int n) {
        if (n == parents[n]) return n;
        else return findParent(parents[n]);
    }

    private static boolean isCommonParent(int x, int y) {
        return findParent(x) == findParent(y);
    }
}