문제 설명

비행정에서 내린 라이캣 일행은 밤을 틈타 라이언 타운에 숨어들었습니다. 사자탈만 쓰고는 관문의 검문을 통과할 수 없다는 것을 라이캣은 이미 알고 있습니다. 목표는 왕족만 드나드는 비밀통로 입구입니다.
"문지기들은 늘 같은 순서로 돈다냥. 순서만 알면 들키지 않고 지나갈 수 있다냥."
"기다릴 때는 기다리고, 갈 때는 단숨에 가는 거다 개굴!"
라이언 타운 골목은 격자 지도 grid로 주어집니다. 각 칸은 다음 중 하나입니다.
'S': 일행이 출발하는 칸 (하나)'E': 비밀통로 입구 (하나)'.': 지나갈 수 있는 길'#': 건물이나 담이라 들어갈 수 없는 칸
문지기들은 k분마다 똑같은 순찰을 되풀이합니다. patrols는 길이 k인 리스트이고, patrols[r]는 시각 t를 k로 나눈 나머지가 r일 때 문지기가 지켜보는 칸들의 [행, 열] 목록입니다. 행과 열 번호는 0부터 셉니다.
일행은 시각 0에 'S' 칸에 있습니다. 1분마다 위·아래·왼쪽·오른쪽으로 한 칸 움직이거나, 제자리에 머뭅니다. 1분이 지난 시각 t에 일행이 있는 칸이 patrols[t % k]에 들어 있으면 들킵니다. 움직이는 도중은 따지지 않고, 매 분이 끝난 시각에 있는 칸만 따집니다.
들키지 않고 비밀통로 입구에 도착하는 가장 빠른 시각을 구하세요. 어떻게 해도 도착할 수 없으면 -1을 반환하세요.
제한 사항
- 입력은
[grid, patrols]형태입니다. - 1 ≤
grid의 행 수, 열 수 ≤ 100이고, 모든 행의 길이가 같습니다. grid에는'S'와'E'가 하나씩 있습니다.- 1 ≤ k =
patrols의 길이 ≤ 10 patrols[r]의 칸은 지도 안에 있고,'#'이나'S'칸은 들어 있지 않습니다.'E'칸은 들어 있을 수 있습니다. 한 목록 안에 같은 칸이 두 번 나오지 않으며, 목록이 비어 있을 수도 있습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| [["S...E"], [[[0, 2]], []]] | 5 |
| [["S.E"], [[[0, 1]]]] | -1 |
| [["S..", ".#.", "..E"], [[[0, 1], [2, 1]], [[1, 0], [1, 2]]]] | 5 |
입출력 설명
첫 번째 예
k = 2입니다. (0, 2) 칸은 시각이 짝수일 때 감시를 받습니다.
| 시각 | 위치 | 설명 |
|---|---|---|
| 0 | (0, 0) | 출발 |
| 1 | (0, 1) | |
| 2 | (0, 1) | 시각 2에는 (0, 2)가 감시받으므로 제자리에서 기다립니다 |
| 3 | (0, 2) | |
| 4 | (0, 3) | |
| 5 | (0, 4) | 비밀통로 입구 도착 |
두 번째 예
k = 1이라 (0, 1) 칸은 언제나 감시를 받습니다. 그 칸을 지나지 않고는 입구에 갈 수 없으므로 -1입니다.
세 번째 예
k = 2입니다. 시각이 짝수이면 (0, 1)·(2, 1), 홀수이면 (1, 0)·(1, 2)가 감시를 받습니다.
| 시각 | 위치 | 설명 |
|---|---|---|
| 0 | (0, 0) | 출발 |
| 1 | (0, 1) | |
| 2 | (0, 2) | (0, 1)에 머물면 들키므로 움직입니다 |
| 3 | (0, 2) | (1, 2)가 감시받으므로 기다립니다 |
| 4 | (1, 2) | |
| 5 | (2, 2) | 비밀통로 입구 도착 |
왼쪽 길로 돌아가면 6분이 걸리므로 답은 5입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | [["S...E"], [[[0, 2]], []]] | 5 |
| 2 | [["S.E"], [[[0, 1]]]] | -1 |
| 3 | [["S..", ".#.", "..E"], [[[0, 1], [2, 1]], [[1, 0], [1, 2]]]] | 5 |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 14개도 함께 채점해요.