Algorithm/BOJ

[BOJ] 복도 뚫기

goakgoak 2020. 10. 21. 16:21

[9373] 복도 뚫기 java

www.acmicpc.net/problem/9373

Solution

  • 넘나 어려운 문제. 답 안 봤으면 절대 못 풀었을거 같다 ㅠ^ㅠ..
  • n개의 센서와 벽을 정점으로 정의하고 벽-센서, 센서-센서를 잇는 간선으로 정의 하여 MST를 만든다.
  • 모든 간선이 들어간 우선순위 큐에서 간선을 뽑으면서 복도를 지나갈 수 있는 센서의 반지름을 구하고 양 벽을 잇는 간선이 나올경우에 프로그램을 종료한다.
  •  양 벽을 잇는 간선의 길이(w)가 복도를 지나갈 수 있는 최대 지름이기 때문이다.

 

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package boj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class _9373 {
   /* boj - 복도 뚫기*/
    static int w, n;
    static int[] parents, x, y, r;
 
    static class Edge implements Comparable<Edge> {
        private int start;
        private int end;
        private double d;
 
        public Edge(int start, int end, double d) {
            this.start = start;
            this.end = end;
            this.d = d;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Double.compare(this.d, o.d);
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = stoi(br.readLine());
 
        for (int t = 0; t < tc; t++) {
            w = stoi(br.readLine());
            n = stoi(br.readLine());
 
            parents = new int[n + 2];
            for (int i = 0; i < parents.length; i++) {
                parents[i] = i;
            }
 
            x = new int[n];
            y = new int[n];
            r = new int[n];
 
            StringTokenizer st;
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                x[i] = stoi(st.nextToken());
                y[i] = stoi(st.nextToken());
                r[i] = stoi(st.nextToken());
            }
 
            PriorityQueue<Edge> pq = new PriorityQueue<>();
            pq.add(new Edge(n, n + 1, w));
            for (int i = 0; i < n; i++) {
                pq.add(new Edge(i, n, Math.max(0, x[i] - r[i])));
                pq.add(new Edge(i, n + 1, Math.max(0, w - x[i] - r[i])));
 
                for (int j = i + 1; j < n; j++) {
                    pq.add(new Edge(i, j, Math.max(0, calcDistance(x[i], x[j], y[i], y[j]) - r[i] - r[j])));
                }
            }
 
            double answer;
            while (!pq.isEmpty()) {
                Edge edge = pq.poll();
                if (union(edge.start, edge.end)) {
                    //  벽과 벽이 이어지면
                    if (find(n) == find(n + 1)) {
                        answer = edge.d/ 2;
                        if (answer == 0) {
                            System.out.println(0);
                        } else {
                            System.out.printf("%6f%n", answer);
                        }
                        break;
                    }
                }
            }
 
        }
    }
 
    private static boolean union(int start, int end) {
        start = find(start);
        end = find(end);
 
        if (start != end) {
            parents[end] = start;
            return true;
        }
        return false;
    }
 
    private static int find(int a) {
        if (parents[a] == a) {
            return a;
        }
        return parents[a] = find(parents[a]);
    }
 
 
    private static double calcDistance(int x1, int x2, int y1, int y2) {
        double d;
        d = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
        return d;
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}
 
 cs