[백준 1944] 복제 로봇 (자바)

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

1944번: 복제 로봇

 

난이도 : 골드 2

 

문제가 복잡하지만 크루스칼 알고리즘으로 풀 수 있습니다.

S, K(포인트라 하겠음) 상관없이 모든 포인트끼리의 거리를 구해 우선순위 큐에 넣으면 됩니다.

BFS를 통해 각 포인트를 출발점으로 해서 도달 가능한 모든 포인트까지의 거리를 구합니다.

 

크루스칼 알고리즘을 돌리고 parent 값(find)은 모두 0이어야 합니다. 만약 0이 아니라면 어느 포인트와도 연결되지 않았다는 것이므로 -1을 출력합니다.

---

전역 변수

int parent[] = 그룹의 대표를 나타내는 배열

int n, m = 지도의 크기와 Key의 개수(S 제외)
char map[][] = 지도의 모양
Key key[] = S, K의 정보가 저장된 배열
PriorityQueue<Edge> pq = 간선을 저장하는 우선순위 큐

함수

void main

입력을 받고 전역 변수들을 세팅해줍니다. S, K값을 key배열에 저장합니다.

간선의 정보를 얻고 크루스칼을 돌립니다. 정답 출력 시 find함수를 이용해 연결 상태를 확인해줍니다.

(getEdge, union, find 호출)

 

void getEdge

포인트로부터 출발하여 각 포인트까지의 거리를 측정합니다. 측정한 거리를 우선순위 큐에 저장합니다.

이 작업은 모든 포인트에서 진행합니다.

 

boolean check

좌표 값의 범위가 정상 범위인지 확인합니다.

 

void union

두 개의 파라미터를 서로 연결합니다. 각 도시의 그룹 대표를 p1, p2로 구합니다.

그리고 그룹의 가장 작은 값이 그룹 대표가 되므로 작은 값을 기준으로 넣어줍니다.

 

int find

입력받은 수의 대푯값을 반환합니다.

재귀를 통해 구현했으며 재귀 과정에서 최적화를 거칩니다. 종료 시점은 파라미터의 대표가 곧 자신일 때(그룹의 가장 작은 수)입니다.

 

class Key

포인트(S, K)의 정보를 저장합니다. 정보는 번호와 좌표입니다.

 

class Edge

간선의 정보를 저장합니다. 연결된 행성 v1, v2와 가중치 weight를 가집니다.

우선순위 큐의 타입이 될 것이므로 Comparable을 implements 해줍니다.

 

class Point

BFS에서 사용될 좌표 타입입니다.

좌표값과 출발지로부터 그 지점까지의 거리를 저장합니다.