[백준 1944번] 복제 로봇

난이도: 골드 II

문제 링크: https://www.acmicpc.net/problem/1944

1944번: 복제 로봇

 

백준 1944번 문제 복제 로봇

 

처음 문제를 읽어보고 나면 어떤 방법으로 접근해야 할지, 조금 막막하게 느껴질 수 있는 문제입니다 (제가 그랬음).

시작점에서 특정 도착점까지의 최단 거리를 구하는 방법에는 여러 가지가 있지만, 이렇게 격자 형식으로 판이 주어지는 경우에는 bfs가 편리합니다.

또, 이런 경우도 있을 수 있습니다. 시작점 S에서 도착점 A, B, C가 있을 때, S->B까지의 거리보다 S->A->B의 거리, 즉 A를 거쳐가는 경우 더 가까울 수도 있죠.

로봇이 복사될 수 있으므로, 로봇이 움직이는 총 횟수를 최소로 한다면, 다음과 같은 아이디어를 생각할 수 있습니다.

"시작점과 모든 열쇠를 최소 비용으로 연결하는 트리 구조"

즉, MST (minimum spanning tree; 최소 신장 트리)의 관점에서 문제를 바라볼 수 있습니다.

 

MST를 구하는 알고리즘 중에서는 kruskal 알고리즘이 유명하지요.

이 알고리즘을 이용하기 위해서는 모든 노드들 간의 거리를 알고, 그 거리를 오름차순으로 정렬해야 합니다.

문제에서 주어진 입력은 grid에 좌표 형식으로 주어지므로, 각 node (시작점 + 열쇠) 간의 최단거리를 구하려면 bfs를 이용하면 됩니다.

 

즉 문제의 접근 순서를 정리하면,

1. 시작점 (0번 노드) 및 열쇠들 (1~번 노드) 사이의 최단거리를 bfs를 통해 구한다. 접근할 수 없는 경우에는 edge를 만들지 않는다.
2. 만들어진 노드의 거리를 오름차순으로 정렬한 후, kruskal을 이용하여 MST를 생성한다.
3. 2를 진행하며 tree에 node를 추가할 때의 edge 값을 누적한다.
4. 모든 node의 parent가 0인지 (=시작점과 연결되어 있는지) 확인한다. 그렇지 않은 경우 -1을 출력한다.
5. 4에서 걸러지지 않은 경우 누적한 거리 값을 정답으로 출력한다.

 

코드로 구현하면 다음과 같습니다.

각 항목마다 주석을 통해 이해를 도왔습니다.

 

이 문제는 두 가지 유형을 동시에 사용해야 하는 문제입니다.

구현에 어려운 점은 전혀 없었으나, 두 방법을 사용하여 해결한다는 발상을 떠올리는 점이 문제 해결의 핵심이라고 생각합니다.

bfs와 mst에 모두 익숙한 상태여야 해결 방법을 쉽게 떠올릴 수 있겠죠?

 

채점 결과

처음에는 node간 거리를 중복해서 구하느라 시간 초과가 발생했고,

두 번째에는 두 node간 최단거리가 존재하지 않는 경우를 고려하지 못하여 틀렸다고 떴었네요.

재밌는 문제였습니다.