Lv.3bfsbitmaskgridshortest-path
열쇠를 모아 미로 탈출하기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
격자 모양의 미로 maze가 주어집니다. maze[i]의 j번째 글자는 i행 j열 칸을 나타냅니다.
| 글자 | 의미 |
|---|---|
S | 출발 칸 (정확히 하나) |
G | 출구 칸 (정확히 하나) |
. | 빈 칸 |
# | 벽 (지나갈 수 없음) |
a ~ f | 열쇠. 그 칸에 들어가면 열쇠를 줍습니다. |
A ~ F | 문. 같은 알파벳의 소문자 열쇠를 가지고 있어야 지나갈 수 있습니다. |
한 번에 상하좌우로 한 칸씩 움직이며, 격자 밖으로는 나갈 수 없습니다. 주운 열쇠는 없어지지 않고 같은 종류의 문을 몇 번이든 열 수 있습니다. 같은 열쇠나 문이 여러 칸에 있을 수도 있습니다.
S에서 G까지 가는 최소 이동 횟수를 반환하세요. 갈 수 없으면 -1입니다.
입출력 예
| maze | result |
|---|---|
["S.A.G", "a####"] | 6 |
["S#G", ".#.", "..."] | 6 |
["SAG", "###"] | -1 |
입출력 예 설명
예 1 — 아래의 열쇠 a를 먼저 줍고(1번) 돌아와서(2번) 문 A를 지나 출구까지 4칸을 더 가면 6번입니다.
예 2 — 벽을 돌아 (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (1,2) → (0,2)로 6번 움직입니다.
예 3 — 문 A를 열 열쇠가 없습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(maze: string[]) → int
제한 사항
-
maze.length,maze[i].length(모든 행의 길이는 같습니다) maze는S,G,.,#,af,AF로만 이루어져 있고,S와G는 정확히 하나씩 있습니다.
기대 복잡도
- 시간
- O(R * C * 2^K)
- 공간
- O(R * C * 2^K)
입출력 예
| maze | 기대 출력 |
|---|---|
["S.A.G","a####"] | 6 |
["S#G",".#.","..."] | 6 |
["SAG","###"] | -1 |
힌트
힌트
같은 칸이라도 어떤 열쇠를 가지고 있는지에 따라 갈 수 있는 곳이 달라집니다. 그래서 "위치"만으로는 상태가 부족합니다.
상태를 (행, 열, 가진 열쇠의 집합)으로 잡으세요. 열쇠는 6종류뿐이므로 집합을 6비트 비트마스크로 나타내면
상태는 최대 개입니다.
이 상태 그래프에서 모든 이동의 비용이 1이므로 BFS로 최단 거리를 구하면 됩니다.
- 열쇠 칸에 들어가면
mask |= 1 << (글자 - 'a') - 문 칸은
mask >> (글자 - 'A') & 1일 때만 들어갈 수 있음 visited[mask][행][열]로 같은 상태를 다시 넣지 않기
G 칸에 처음 도착한 순간의 거리가 답입니다.
복잡도 목표
모든 상태의 거리를 더 이상 바뀌지 않을 때까지 반복해서 고치는 풀이는 길이 긴 미로에서 효율성 테스트 시간을 넘깁니다. BFS는 입니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1000 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 13 | 판정만 |
| performance | 60 | 4 | 판정만 |