본문 바로가기

알고리즘

왕가의 비밀통로

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

왕가의 비밀통로

문제 설명

라이언 타운에 숨어든 라이캣 일행은 왕궁 지하로 이어지는 왕가의 비밀통로 앞에 섰습니다. 길잡이는 뮤라입니다. 뮤라는 타임 스톤을 받은 뒤 하티·지지와 함께 이 통로 깊은 곳까지 들어갔다가, 흑마법으로 깨어난 좀비 떼에 갇힌 적이 있습니다. 그때 타임 스톤으로 시간을 몇 번이고 되돌리며 통로 지도를 완성해 두었지요.

"좀비가 서 있는 칸은 절대 밟으면 안 돼. 잠긴 문은 같은 문양의 횃불 열쇠가 있어야 열려."

"그럼 횃불을 전부 주워 가면 되는 거냥?"

"그러다 해가 뜨겠다 개굴. 필요한 횃불만 주워서 가장 짧게 가자 개굴!"

통로 지도 data는 문자열 리스트입니다. data[r]의 c번째 문자가 r행 c열 칸이고, 각 문자의 뜻은 다음과 같습니다.

문자뜻
@비밀통로 입구(일행이 출발하는 칸)
*왕궁 지하로 나가는 출구
.빈 칸
#무너진 돌벽
Z흑마법 좀비
a~f횃불 열쇠
A~F잠긴 문

일행은 다음 규칙으로 움직입니다.

  1. 한 번에 위·아래·왼쪽·오른쪽 중 한 방향으로 한 칸 움직이고, 이것을 이동 1번으로 셉니다. 지도 밖으로는 나갈 수 없습니다.
  2. # 칸과 Z 칸에는 들어갈 수 없습니다.
  3. 횃불 열쇠 칸에 들어서면 그 열쇠를 줍습니다. 줍는 데 이동은 들지 않고, 주운 열쇠는 끝까지 가지고 다닙니다.
  4. 잠긴 문 칸에는 같은 알파벳의 열쇠를 가지고 있을 때만 들어갈 수 있습니다(B 문은 b 열쇠). 열쇠는 써도 없어지지 않으므로, 같은 알파벳 문이 여러 개 있어도 열쇠 하나로 모두 지날 수 있습니다.
  5. @ 칸, . 칸, 열쇠 칸은 언제든 지나갈 수 있고, 같은 칸을 여러 번 지나가도 됩니다. * 칸에 들어서면 탈출합니다.

입구 @에서 출구 *까지 가는 가장 적은 이동 횟수를 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개도 함께 채점해요.