복도뚫기 java
-
[BOJ] 복도 뚫기Algorithm/BOJ 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..