문제 설명

라이언 타운에 숨어든 라이캣 일행은 왕궁 지하로 이어지는 왕가의 비밀통로 앞에 섰습니다. 길잡이는 뮤라입니다. 뮤라는 타임 스톤을 받은 뒤 하티·지지와 함께 이 통로 깊은 곳까지 들어갔다가, 흑마법으로 깨어난 좀비 떼에 갇힌 적이 있습니다. 그때 타임 스톤으로 시간을 몇 번이고 되돌리며 통로 지도를 완성해 두었지요.
"좀비가 서 있는 칸은 절대 밟으면 안 돼. 잠긴 문은 같은 문양의 횃불 열쇠가 있어야 열려."
"그럼 횃불을 전부 주워 가면 되는 거냥?"
"그러다 해가 뜨겠다 개굴. 필요한 횃불만 주워서 가장 짧게 가자 개굴!"
통로 지도 data는 문자열 리스트입니다. data[r]의 c번째 문자가 r행 c열 칸이고, 각 문자의 뜻은 다음과 같습니다.
| 문자 | 뜻 |
|---|---|
@ | 비밀통로 입구(일행이 출발하는 칸) |
* | 왕궁 지하로 나가는 출구 |
. | 빈 칸 |
# | 무너진 돌벽 |
Z | 흑마법 좀비 |
a~f | 횃불 열쇠 |
A~F | 잠긴 문 |
일행은 다음 규칙으로 움직입니다.
- 한 번에 위·아래·왼쪽·오른쪽 중 한 방향으로 한 칸 움직이고, 이것을 이동 1번으로 셉니다. 지도 밖으로는 나갈 수 없습니다.
#칸과Z칸에는 들어갈 수 없습니다.- 횃불 열쇠 칸에 들어서면 그 열쇠를 줍습니다. 줍는 데 이동은 들지 않고, 주운 열쇠는 끝까지 가지고 다닙니다.
- 잠긴 문 칸에는 같은 알파벳의 열쇠를 가지고 있을 때만 들어갈 수 있습니다(
B문은b열쇠). 열쇠는 써도 없어지지 않으므로, 같은 알파벳 문이 여러 개 있어도 열쇠 하나로 모두 지날 수 있습니다. @칸,.칸, 열쇠 칸은 언제든 지나갈 수 있고, 같은 칸을 여러 번 지나가도 됩니다.*칸에 들어서면 탈출합니다.
입구 @에서 출구 *까지 가는 가장 적은 이동 횟수를 return 하세요. 출구에 갈 수 없으면 -1을 return 하세요.
제한 사항
data의 길이(세로)는 1 이상 50 이하입니다. 모든 문자열의 길이(가로)는 같고, 1 이상 50 이하입니다.- 문자열에는 위 표에 있는 문자만 들어 있습니다.
@와*는 정확히 하나씩 있습니다.- 같은 알파벳의 열쇠는 많아야 하나입니다. 문은 같은 알파벳이 여러 개 있을 수 있고, 지도에 열쇠가 없는 문도 있을 수 있습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| ["@..a", "#Z#.", "*A.."] | 8 |
| ["@..Z.b", ".#####", "...B*."] | -1 |
| ["a.#..*", ".@#B##", "#.A..b"] | 15 |
입출력 설명
입출력 예 #1
@..a
#Z#.
*A..
입구 아래는 돌벽이고 출구 * 옆은 A 문이라, a 열쇠를 주워 A 문을 지나야만 출구에 갈 수 있습니다. 오른쪽으로 3번 가서 a를 줍고, 아래로 2번, 왼쪽으로 3번(A 문을 지나) 가면 출구입니다. 3 + 2 + 3 = 8번입니다.
입출력 예 #2
@..Z.b
.#####
...B*.
출구 *에 들어가려면 B 문을 지나야 하는데, b 열쇠로 가는 길은 좀비 Z가 막고 있습니다. 출구에 갈 수 없으므로 -1입니다.
입출력 예 #3
a.#..*
.@#B##
#.A..b
출구로 가려면 B 문을 지나야 하고, b 열쇠는 A 문 너머에 있습니다. 그래서 a 열쇠까지 2번, A 문까지 4번, b 열쇠까지 3번, 다시 B 문을 지나 출구까지 6번, 모두 15번 움직입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | ["@..a", "#Z#.", "*A.."] | 8 |
| 2 | ["@..Z.b", ".#####", "...B*."] | -1 |
| 3 | ["a.#..*", ".@#B##", "#.A..b"] | 15 |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 15개도 함께 채점해요.