쿠키크루
면접 대비시간 제한1초메모리 제한512 MB
각 토핑이 세 개씩 있는 N x N 격자에서 집에서 목표까지 같은 토핑 세 개를 모두 거치는 최단 경로가 가장 짧은 토핑 종류를 찾는다.
문제
밀가루반죽으로 잘 구워진 킴쿠키는 넓고 평평한 들판 위에 세워진 쿠키나라의 시민이다. 킴쿠키는 케이크나라의 침략으로 어려워진 쿠키나라를 지키기 위해 할 수 있는 일이 없을까 늘 고민했다. 그러던 어느 날, 고민하며 산책하던 킴쿠키는 쿠키나라의 기사단인 쿠키크루를 모집한다는 전단지를 발견하였다. 쿠키크루에 지원하려면 지원 분야에 맞는 토핑 3개를 몸에 두르고 있어야 한다. 쿠키크루의 지원 분야와 어울리는 토핑은 다음과 같다.
- 침투단(Assassin) - 젤리(J)
- 치유단(Healer) - 초콜릿(C)
- 마법단(Mage) - 베리(B)
- 방어단(Tanker) - 호두(W)
킴쿠키는 쿠키크루에 가입하기로 마음을 먹었지만 경쟁률이 높기 때문에 최대한 빠르게 지원해야 한다. 킴쿠키는 서둘러 집으로 돌아가 N × N 크기의 2차원인 토핑토핑지도를 꺼내 각 토핑의 위치를 확인하였다. 지도에는 호두, 초콜릿, 베리, 젤리 토핑의 위치가 각각 3개씩 표시되어 있고 집(H)의 위치, 그리고 쿠키크루에 지원하는 장소인 쿠키크루삥뽕(#)이 표시되어 있다. 킴쿠키는 지도를 보고 토핑이 떨어져 있는 위치를 확인한 다음, 같은 종류의 토핑 3개를 몸에 두르고 쿠키크루삥뽕에 가야 한다.
최대한 빠르게 쿠키크루에 지원하고 싶어 하는 킴쿠키를 위해, 지도를 보고 킴쿠키가 지원해야 하는 분야를 알려주자.
킴쿠키는 지도상에서 상, 하, 좌, 우로 움직일 수 있으며 한 번에 한 칸 움직일 수 있고 같은 곳을 여러 번 들를 수 있다.
쿠키크루삥뽕에 도착했을 때, 지원하려는 분야 이외의 토핑이 몸에 추가로 둘러져 있어도 상관없으며 아직 지원할 수 없는 상황에서도 쿠키크루삥뽕을 거쳐 다른 곳으로 이동할 수 있다.
입력
입력의 첫 번째 줄에는 토핑토핑지도의 크기 N이 주어진다. (4 ≤ N ≤ 100)
입력의 두 번째 줄부터 N개의 줄에 N칸에 걸쳐 토핑토핑지도가 주어진다. 지도에서 X은 빈 땅, H는 집, W, C, B, J는 각각 호두, 초콜릿, 베리, 젤리 토핑이며 #은 쿠키크루에 지원하는 장소인 쿠키크루삥뽕이다.
지도에는 각 토핑이 3개씩 있고 집과 쿠키크루삥뽕이 하나씩 있음이 보장된다.
출력
킴쿠키가 지원해야 하는 분야를 출력한다.
침투단에 지원해야 하면 "Assassin", 치유단이면 "Healer", 마법단이면 "Mage", 방어단이면 "Tanker"를 출력한다.
지원할 수 있는 분야가 여러 개라면 침투단, 치유단, 마법단, 방어단 순서로 우선순위를 둔다.