링크
문제 요약
로봇 $n$개가 $h$행 $w$열 크기의 격자에 놓여있다. 각 격자는 막혀있거나, 비어있거나, 회전판이 존재한다. 로봇을 밀면 로봇은 벽을 만날때까지 계속해서 움직이고, 회전판을 만나면 방향을 바꾸어 진행한다. 또한 멈춘 지점에 다른 로봇과 결합이 가능한 상태의 경우 해당 로봇과 결합한다. 이때 연속적인 번호를 가진 로봇이 해당 격자에 빠짐없이 나타날 때, 로봇은 결합할 수 있다. 즉, $a$번 부터 $b$번까지 모든 로봇이 하나의 격자에 있으면, 이는 $a-b$ 로봇으로 결합한다. 주어진 상태에서 $1-n$ 로봇을 만들기 위한 최소 이동횟수를 구하여라. 불가능한 경우 -1을 출력한다.
관찰
먼저 가장 먼저 드는 생각은 각 격자에서 특정 방향으로 로봇을 이동시키면 어떤 격자에서 멈추는지를 결정해야 한다. 혹은 멈추지 못하고 무한히 특정 경로를 돌 수도 있을 것이다. 만약 해당 정보를 구했다면, 이젠 어떤식으로 로봇을 합칠지 생각해야한다. 로봇을 합칠때는 번호가 연속해야 하므로, $1-n$을 만들기 위해서는 반드시, 어떤 $1\le c < n$ 에 대하여, $1-c$ 로봇과 $(c+1)-n$ 로봇을 합쳤을 것이다. 또한, 각 로봇이 어떤 위치에 있는지에 따라 어디서 합쳐야 최적인지가 달라질 것이다. 따라서 이 과정은 로봇의 정보와 위치에 대하여 DP를 수행하면 풀릴 것으로 추측할 수 있다.
풀이
각 격자에서 특정 방향으로 로봇을 이동시킬 때 어떤 격자에서 멈추는지는 DP와 BFS를 통해 계산이 가능하다. 우선 큐에 각 격자마다, 1칸을 특정 방향으로 진행하였을 때 더 이상 이동할 수 없는 위치를 넣는다. 즉, 이렇게 큐에 들어간 정보는 로봇이 어떤 위치에서 특정 방향으로 이동 후 멈춘다면, 멈추게 되는 위치의 후보를 의미한다. 이후 BFS를 돌면서, 현재 정점(=격자 위치와 방향)의 정보를 기반으로 현재 정점에 오기 위해 이전 정점의 정보를 역산할 수 있다. 이 과정을 반복하여 $NXT(i,j,dir)=i$행 $j$열에 위치한 로봇을 $dir$ 방향으로 밀 때 멈추는 격자를 모두 구할 수 있다. 만약 BFS를 수행하면서 방문이 되지 않은 정점은 해당 방향으로 이동 시 사이클이 형성되어 있다는 사실도 얻을 수 있게 된다.
다음으로 최소 이동 횟수를 구하는 방법을 생각해보자. 앞서 관찰한 내용에서 아래와 같은 점화식을 정의할 수 있다.
$D(l,h,r,c)=$ $l-h$ 로봇이 $r$행 $c$열의 격자에 위치하도록 만드는 최소 이동 횟수
기본적으로 $l-h$ 로봇을 만들기 위해서는 $l \le m < h$ 인 $m$에 대하여, 로봇 $l-m$ 와 로봇 $(m+1)-h$를 합쳐야 함을 알 수 있다. 또한 로봇이 합체되는 시점은 $r$행 $c$열의 격자일 수도 있고, 그 이전에 합체후 해당 위치로 이동하는 2가지 경우가 존재한다. 우선 첫번째 경우에 기반하여 점화식을 세워보면 아래와 같다.
$D(l,h,r,c)=\min (D(l,m,r,c)+D(m+1,h,r,c)) \hspace{1em} (l \le m < h)$
이제 $r$행 $c$열의 격자에 오기 전에 합체후 이동한 경우를 생각해보자. 이는 어떤 위치 $r’$행 $c’$열까지는 첫번째 방식으로 이동하고, 이후 최단 경로로 $r$행 $c$열까지 이동하는 것임을 알 수 있다. 따라서 앞서 점화식으로 계산된 모든 값을 초기값으로 넣고 다익스트라를 수행하여 두번째 방식을 통한 최소 이동 횟수도 계산이 가능하다. 하지만 시간 제한이 빡빡하기 때문에 BFS를 통해 해당 과정을 수행해야 되고, 거리 값에 따라 큐를 여러개 두는 식으로 구현이 가능하다.
전체 풀이에 걸리는 시간을 정리하면 다음과 같다.
- $NXT(i,j,dir)$를 채우는데 걸리는 시간이 $O(4HW)$
- DP를 수행할 $l$과 $h$를 결정하는게 $O(N^2)$이고 각 $l$과 $h$에 대하여 아래만큼 시간이 걸린다.
2-1. 점화식에 기반하여 DP를 수행하는데 드는 시간이 $O(NHW)$
2-2. BFS로 업데이트 하는데 걸리는 시간이 $O(HW)$
따라서 전체 시간 복잡도 $O(4HW+N^2(NHW+HW))=O(N^3HW+4HW)$ 에 문제가 해결된다.