본문 바로가기

알고리즘

라이언 타운 잠입

New Era · 5번Lv. 4그래프 탐색(BFS·DFS)

라이언 타운 잠입

문제 설명

비행정에서 내린 라이캣 일행은 밤을 틈타 라이언 타운에 숨어들었습니다. 사자탈만 쓰고는 관문의 검문을 통과할 수 없다는 것을 라이캣은 이미 알고 있습니다. 목표는 왕족만 드나드는 비밀통로 입구입니다.

"문지기들은 늘 같은 순서로 돈다냥. 순서만 알면 들키지 않고 지나갈 수 있다냥."

"기다릴 때는 기다리고, 갈 때는 단숨에 가는 거다 개굴!"

라이언 타운 골목은 격자 지도 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개도 함께 채점해요.