[백준][BOJ1944] 복제 로봇

Algorithm/Kruskal

by bedamino 2021. 7. 5. 22:19

1. 문제 : https://www.acmicpc.net/problem/1944

1944번: 복제 로봇

첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어

www.acmicpc.net

2. 풀이 : Kruskal + BFS

3. 설명

출발 지점에서 로봇과 복제된 로봇이 열쇠까지 이동하는 최단 거리와, 열쇠가 있는 지점에서 복제된 로봇이 다른 열쇠가 있는 지점까지 이동하는 최단 거리를 표현하면 그림[1]과 같다. 각각의 최단 거리는 S지점과, K지점에서의 BFS로 구할 수 있다.

출발 지점과 열쇠가 있는 지점을 넘버링하여 표현을 하면 그림[2]와 같다. 로봇이 모든 열쇠를 최소의 움직임으로 찾기 위해서는 위의 그래프에서 MST를 생성했을 때이다.

그림[3]과 같이 6번의 움직임으로 모든 열쇠를 찾을 수 있으며, 이 때의 움직임이 최소 횟수가 된다. MST는 간선의 수가 '노드의 수 - 1'이므로, MST를 생성하였을 때 간선의 수가 '노드의 수 - 1'보다 적다면 로봇은 모든 열쇠를 찾을 수 없다.

4. 코드

저작자표시 비영리 변경금지