[백준] 달이 차오른다, 가자. (1194번)

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

예제 입력 1 복사

1 7 f0.F..1

예제 출력 1 복사

7

---

전형적인 탈출하기 bfs 문제이다.

문제는 지도에서 문과 열쇠가 등장하는데 열쇠가 있어야만 문을 열 수 있다는 게 이 문제의 특이한 점이다.

열쇠 소유 여부를 기록하기 위해 벡터를 써봤는데, 결국 방문 여부를 기록하는 visit 배열에 좌표 뿐만 아니라 열쇠 소유 여부까지 기록을 해야해서 비트마스크를 사용했다.

 

지도는 int 로 다루는 게 간단해서 모든 값을 int로 변환했다. 0은 이동가능, 1은 탈출지점, 2는 벽, 10~15는 각각 A, B, C...F에 대응되고 100~105는 a~f에 대응된다. 여기에 비트 마스크를 이용해 각 인덱스별로 a~f 열쇠에 대응되게 했다.

즉 000100 이라면 세번째 열쇠만 있으니 c 열쇠가 있다는 뜻이다. 

 

이런식으로 열쇠가 있을때에만 문을 열고 넘어갈 수 있음을 항상 체크하고 bfs를 돌리면 답을 구할 수 있다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%8B%AC%EC%9D%B4%20%EC%B0%A8%EC%98%A4%EB%A5%B8%EB%8B%A4%2C%20%EA%B0%80%EC%9E%90%20(1194%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;

int N, M;
int p[51][51]; // 0 : 이동가능, 1 : 탈출구, 2 : 벽, 10~15 : A~F, 100~105 : a~f
int visit[51][51][1<<6];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
int sx, sy; //시작 위치
int res = 987654321; // 결과값

struct pos {
	int x, y, dist; // 좌표, 이동거리
	int key = 0; // 열쇠 소유 여부 [A,B, ... , F]
};

void bfs() {
	memset(visit, -1, sizeof(visit));
	queue<pos> q;
	q.push({ sx,sy,0, 0 });
	visit[sx][sy][0] = 0;
	
	while (!q.empty()) {
		pos cur = q.front();
		q.pop();

		if (p[cur.x][cur.y] == 1) {
			res = min(res, visit[cur.x][cur.y][cur.key]);
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i];
			int ny = cur.y + dy[i];
			if (nx<1 || ny<1 || nx>N || ny>M) continue; // 범위 벗어나면 continue
			if (p[nx][ny] == 2) continue; // 벽이면 건너갈 수 없다.
			if (p[nx][ny] == 0 || p[nx][ny] == 1) {
				if (visit[nx][ny][cur.key] != -1) continue;
				q.push({ nx,ny,cur.dist + 1,cur.key });
				visit[nx][ny][cur.key] = cur.dist + 1;
			}
			else if (p[nx][ny] >= 10 && p[nx][ny] <= 15) { // 문
				int needKey = 1<<(p[nx][ny] - 10); // 문을 여는데 필요한 열쇠 인덱스
				if ((cur.key & needKey) == 0) continue; //열쇠 없으면 못간다.
				if (visit[nx][ny][cur.key | needKey] != -1) continue; // 이미 방문했으면 continue
				q.push({ nx,ny,cur.dist + 1,cur.key|needKey });
				visit[nx][ny][cur.key | needKey] = cur.dist + 1;
			}
			else { // 열쇠
				int nextKey = 1<<(p[nx][ny] - 100);
				if (visit[nx][ny][cur.key | nextKey] != -1) continue;
				q.push({ nx,ny,cur.dist + 1,cur.key|nextKey });
				visit[nx][ny][cur.key|nextKey] = cur.dist + 1;
			}
		}
	}
}

int main()
{
	cin >> N >> M;
	string str;
	for (int i = 1; i <= N; i++) {
		cin >> str;
		for (int j = 1; j <= M; j++) {
			char cur = str[j - 1];
			if (cur == '.')
				p[i][j] = 0;
			else if (cur == '#')
				p[i][j] = 2;
			else if (cur == '0') {
				sx = i, sy = j;
				p[i][j] = 0;
			}
			else if (cur == '1') {
				p[i][j] = 1;
			}
			else if (cur >= 'A' && cur <= 'F')
				p[i][j] = cur - 'A' + 10;
			else
				p[i][j] = cur - 'a' + 100;
		}
	}

	bfs();

	if (res == 987654321)
		cout << -1;
	else
		cout << res;
}