Funcia
Lv.3bfsbitmaskgridshortest-path

열쇠를 모아 미로 탈출하기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

격자 모양의 미로 maze가 주어집니다. maze[i]의 j번째 글자는 i행 j열 칸을 나타냅니다.

글자의미
S출발 칸 (정확히 하나)
G출구 칸 (정확히 하나)
.빈 칸
#벽 (지나갈 수 없음)
a ~ f열쇠. 그 칸에 들어가면 열쇠를 줍습니다.
A ~ F문. 같은 알파벳의 소문자 열쇠를 가지고 있어야 지나갈 수 있습니다.

한 번에 상하좌우로 한 칸씩 움직이며, 격자 밖으로는 나갈 수 없습니다. 주운 열쇠는 없어지지 않고 같은 종류의 문을 몇 번이든 열 수 있습니다. 같은 열쇠나 문이 여러 칸에 있을 수도 있습니다.

S에서 G까지 가는 최소 이동 횟수를 반환하세요. 갈 수 없으면 -1입니다.

입출력 예

mazeresult
["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

제한 사항

  • 1≤R=1 \le R = maze.length ≤100\le 100, 1≤C=1 \le C = maze[i].length ≤100\le 100 (모든 행의 길이는 같습니다)
  • 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비트 비트마스크로 나타내면 상태는 최대 100×100×26=640,000100 \times 100 \times 2^6 = 640{,}000개입니다.

이 상태 그래프에서 모든 이동의 비용이 1이므로 BFS로 최단 거리를 구하면 됩니다.

  • 열쇠 칸에 들어가면 mask |= 1 << (글자 - 'a')
  • 문 칸은 mask >> (글자 - 'A') & 1일 때만 들어갈 수 있음
  • visited[mask][행][열]로 같은 상태를 다시 넣지 않기

G 칸에 처음 도착한 순간의 거리가 답입니다.

복잡도 목표

모든 상태의 거리를 더 이상 바뀌지 않을 때까지 반복해서 고치는 풀이는 길이 긴 미로에서 효율성 테스트 시간을 넘깁니다. BFS는 O(R⋅C⋅2K)O(R \cdot C \cdot 2^K)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251000 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4013판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.