창고지기
면접 대비시간 제한1초메모리 제한1024 MB
10칸짜리 창고에서 로봇이 상자를 목표 칸까지 밀어 옮기는 최소 명령 횟수를 구하고, 불가능하면 -1을 답합니다.
문제
인하대학교의 자료구조와 알고리즘 연구 소모임 CTP는 스터디에 필요한 비품을 좁은 창고에 보관하고 있다. 창고는 아래 그림과 같이 일렬로 늘어선 크기의 칸 개로 이루어져 있다. 각 칸에는 로봇이나 박스가 하나 있을 수 있으며, 창고에는 로봇과 박스가 정확히 하나씩 있다.
CTP의 창고지기 시은이는 로봇에게 명령을 내려 박스를 원하는 칸으로 옮기려고 한다. 로봇에게 내릴 수 있는 명령은 다음 두 종류이다.
- 인접한 빈칸으로 이동한다.
- 인접한 칸의 박스를 밀어서, 박스가 있던 칸으로 이동한다. 박스는 밀려날 때 로봇이 없는 인접한 칸으로 이동한다. 박스를 밀어낼 칸이 없으면 이 명령은 실패한다.
위 그림의 경우 명령 두 번으로 박스를 원하는 칸(깃발로 표시)으로 옮길 수 있다. 창고의 상태가 주어질 때, 박스를 원하는 칸에 두기 위해 최소 몇 번의 명령이 필요한지 알아보자.
입력
첫 번째 줄에 창고의 상태를 나타내는 10개의 문자가 주어진다.
각 문자는 ., @, #, ! 중 하나이며, 각각 빈칸, 로봇이 있는 칸, 박스가 있는 칸, 박스를 놓아야 하는 칸을 뜻한다.
@, #, !는 정확히 하나씩 주어진다. 즉, 박스가 처음부터 목표 지점에 있는 경우는 주어지지 않는다.
출력
박스를 원하는 칸에 둘 수 있는 최소 명령 횟수를 출력한다.
명령을 몇 번 내려도 박스를 원하는 칸으로 옮길 수 없다면 대신 -1을 출력한다.