문제
지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.
민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.
하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.
영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.
민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.
- 빈 칸: 언제나 이동할 수 있다. (’.’)
- 벽: 절대 이동할 수 없다. (’#’)
- 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’)
- 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. (‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’)
- 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. (‘0’)
- 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (‘1’)
달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.
민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. ‘0’은 한 개, ‘1’은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.
출력
첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.
예제 입력 1
1 7
f0.F..1예제 출력 1
7예제 입력 2
5 5
....1
#1###
.1.#0
....A
.1.#.예제 출력 2
-1예제 입력 3
7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1예제 출력 3
55예제 입력 4
3 4
1..0
###.
1...예제 출력 4
3예제 입력 5
3 5
..0..
.###.
..1.A예제 출력 5
6예제 입력 6
4 5
0....
.#B#A
.#.#.
b#a#1예제 출력 6
19예제 입력 7
1 11
c.0.C.C.C.1예제 출력 7
12예제 입력 8
3 6
###...
#0A.1a
###...예제 출력 8
-1노트
- 단순히 현재 얻은 키 상태만으로는 어렵고, 지금까지 갖고 있는 키 상태에서 탐색을 해야한다.
- 키가 6개의 보유 상태를 하나의 변수에 비트마스킹으로 표현하면 65개의 상태가 있을 수 있다 (보유 키 조합 64 + 아무 키도 보유하지 않음 1)
#include <algorithm>
#include <iostream>
#include <queue>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)
#define BIG_NUMBER 987654321
#define MAX 51
#define NOT_VISITED -1
#define WALL '#'
#define EMPTY '.'
#define START '0'
#define EXIT '1'
int board[MAX][MAX];
int dist[MAX][MAX][65];
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
int N, M;
struct State {
int r;
int c;
short hasKey;
};
int bfs(State start) {
std::queue<State> Q;
auto [sr, sc, sHasKey] = start;
dist[sr][sc][sHasKey] = 0;
Q.push(start);
int min_dist = BIG_NUMBER;
while (!Q.empty()) {
auto [qr, qc, qHasKey] = Q.front();
Q.pop();
if (board[qr][qc] == EXIT) {
min_dist = std::min(min_dist, dist[qr][qc][qHasKey]);
}
for (int i = 0; i < 4; i++) {
int nr = qr + dr[i];
int nc = qc + dc[i];
if (0 <= nr && nr < N && 0 <= nc && nc < M) {
char next = board[nr][nc];
bool canMove = next == EMPTY || next == START || next == EXIT;
// 그냥 빈공간은 나아가기
if (canMove && dist[nr][nc][qHasKey] == NOT_VISITED) {
dist[nr][nc][qHasKey] = dist[qr][qc][qHasKey] + 1;
Q.push({nr, nc, qHasKey});
}
// 열쇠가 있을 때
if (97 <= next && next < 103) {
char nCurKey = next - 97 + 1;
short nHasKey = qHasKey | (1 << nCurKey);
if (dist[nr][nc][nHasKey] == NOT_VISITED) {
dist[nr][nc][nHasKey] = dist[qr][qc][qHasKey] + 1;
Q.push({nr, nc, nHasKey});
}
}
// 문이 있을 때
if (65 <= next && next < 71) {
char requiredKey = next - 65 + 1;
if (qHasKey & (1 << requiredKey)) {
if (dist[nr][nc][qHasKey] == NOT_VISITED) {
dist[nr][nc][qHasKey] = dist[qr][qc][qHasKey] + 1;
Q.push({nr, nc, qHasKey});
}
}
}
}
}
}
return min_dist;
}
void solve() {
std::cin >> N >> M;
State start = {-1, -1, 0};
std::string x;
for (int r = 0; r < N; r++) {
std::cin >> x;
for (int c = 0; c < M; c++) {
board[r][c] = x[c];
if (x[c] == START) {
start.r = r;
start.c = c;
}
}
}
std::fill(&dist[0][0][0], &dist[0][0][0] + (MAX * MAX * 65), NOT_VISITED);
int result = bfs(start);
std::cout << (result == BIG_NUMBER ? -1 : result);
}
int main() {
IO;
solve();
return 0;
}