[BOJ]9373번 : 복도 뚫기

https://www.acmicpc.net/problem/9373

9373번: 복도 뚫기

 

분류 : 최소 스패닝 트리, 이분 탐색

import java.io.*;
import java.math.*;
import java.util.*;

class Myscanner {
    BufferedReader br;
    StringTokenizer st;

    public Myscanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {
    public static Myscanner sc = new Myscanner();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    public static int[] uf = new int[1002];

    public static void main(String[] args) throws IOException {
        int TC = sc.nextInt();
        while (TC-- > 0) {
            int W = sc.nextInt();
            int N = sc.nextInt();
            Queue<Edge> pq = new PriorityQueue<Edge>();
            Vector<Point> v = new Vector<>();
            for (int i = 0; i < N; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int r = sc.nextInt();
                v.add(new Point(x, y, r));
            }
            pq.add(new Edge(W, N, N + 1));
            for (int i = 0; i < N; i++) {
                pq.add(new Edge(Math.max(0, v.get(i).x - v.get(i).r), i, N));
                pq.add(new Edge(Math.max(0, W - v.get(i).x - v.get(i).r), i, N + 1));

                for (int j = 0; j < i; j++) {
                    double cc = calc(v.get(i).x, v.get(i).y, v.get(j).x, v.get(j).y);
                    pq.add(new Edge(Math.max(0.0, cc - v.get(i).r - v.get(j).r), j, i));
                }
            }
            Arrays.fill(uf, -1);
            while (!pq.isEmpty()) {
                Edge e = pq.poll();
                if (uf_union(e.node1, e.node2)) {
                    if (uf_find(N) == uf_find(N + 1)) {
                        if (e.dist == 0)
                            out.println(0);
                        else
                            out.printf("%.6f\n", e.dist / 2);
                        break;
                    }
                }
            }
        }
        out.flush();
    }

    public static double calc(double x1, double y1, double x2, double y2) {
        return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
    }

    static int uf_find(int a) {
        if (uf[a] < 0)
            return a;
        return uf[a] = uf_find(uf[a]);
    }

    static boolean uf_union(int a, int b) {
        a = uf_find(a);
        b = uf_find(b);
        if (a == b)
            return false;

        if (uf[a] < uf[b]) {
            uf[a] += uf[b];
            uf[b] = a;
        } else {
            uf[b] += uf[a];
            uf[a] = b;
        }
        return true;
    }
}

class Edge implements Comparable<Edge> {

    double dist;
    int node1;
    int node2;

    Edge(double dist, int node1, int node2) {
        this.dist = dist;
        this.node1 = node1;
        this.node2 = node2;
    }

    @Override
    public int compareTo(Edge o) {
        return dist < o.dist ? -1 : 1;
    }
}

class Point {
    int x;
    int y;
    int r;

    Point(int x, int y, int r) {
        this.x = x;
        this.y = y;
        this.r = r;
    }
}

최소 스패닝 트리를 공부하게 되면서 같이 공부하는 스터디원과 이 문제를 잡고 풀어보기로 했다.

아무리 생각해도 답이 안 나오길래 검색을 해보았고 http://m.blog.naver.com/kks227/220718299440 이분의 블로그를 참고하여 문제를 이해하고 풀어나갔다.

답을 보면서 까지 했는데도 4~5시간동안 고민과 토론 끝에 통과 완료. (설명을 잘 적어주셔서 감사합니다 ㅠㅠ)

정말... 저 분이 없었더라면 죽어도 못 맞췄을 문제라고 생각한다.

만약 문제를 풀게 된다면 예제의 테스트 케이스와 "질문 검색"에 있는 반례를 확실히 해결할 수 있어야 한다.