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

 

문제

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

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

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

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

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

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

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

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

입력

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

출력

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

 

두번째 풀이에 통과했습니다.

시간초과한 첫번째 풀이입니다.

#include<bits/stdc++.h>

using namespace std;
typedef tuple<int, int, int, int> ti;
typedef pair<int, int> pi;
int n, m;
char mp[51][51];
int v[51][51];
int dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	queue<ti>q;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
			if (mp[i][j] == '0')q.push({ i,j,0,0 });  //y,x,dist,key 튜플에 입력
            //큐 q는 각 bfs시 출발 지점을 넣어놓습니다.
		}
	}
	int ans = INT_MAX;
	
	while (!q.empty()) {
		auto [Y,X, Dist,keys] = q.front(); q.pop(); //각q의 top요소에 대해
		int tempKeys = keys;
		memset(v, 0, sizeof(v));
		v[Y][X] = Dist;
		queue<pi>q2; //q2는 BFS를 이용한 길찾기를 위한 큐입니다. 출발지점 q.top을 넣습니다
		q2.push({ Y,X });
		while (!q2.empty()) {
			auto [y, x] = q2.front(); q2.pop();
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
					if (!v[ny][nx] && mp[ny][nx] != '#') { //벽이아니고, 미방문인경우
						if (mp[ny][nx] == '1') { //도착지점인경우
							ans = min(ans, v[y][x]+1);
					
						}
						else if ('A' <= mp[ny][nx] && mp[ny][nx] <= 'F') { //문인경우
							if (keys & 1 << (mp[ny][nx] - 'A')) { //비트마스크. 열쇠가 있으면
								v[ny][nx] = v[y][x] + 1;
								q2.push({ ny,nx });
							}
						}
						else if ('a' <= mp[ny][nx] && mp[ny][nx] <= 'f') {//열쇠인경우
							if (!(keys & 1 << (mp[ny][nx] - 'a'))) {//비트마스크. 없는열쇠면
								tempKeys = keys;
								tempKeys |= (1 << (mp[ny][nx] - 'a'));//열쇠를 획득,							
								q.push({ ny,nx,v[y][x]+1,tempKeys });//열쇠를 획득한 지점으로부터 
                               //새로 열 수 있는 문이 있는지 확인하기위해, q에 열쇠를 획득한 지점을 넣습니다.
							}
							v[ny][nx] = v[y][x] + 1;
							q2.push({ ny,nx });
						}
						else {
							v[ny][nx] = v[y][x] + 1; //빈공간이면
							q2.push({ ny,nx });
						}
					}
				}
			}
		}
	}
	ans == INT_MAX ? cout << -1 : cout << ans;
}

while문 내부에 BFS를 수행해서 그런지,,,,

테스트케이스는 모두 통과했는데 시간초과가 났습니다.

비트마스크를통해 보유한 키를 표시했고,

열쇠를 얻은 그 좌표부터 다시 BFS를 수행하기위해 큐에 좌표와,열쇠획득 정보를 넣었습니다.

 

열쇠를 얻은 좌표에서 이동해서 문을 여는 수행을 반복해야하는데,

통과한 두번째 풀이는 아래와 같습니다

#include<bits/stdc++.h>

using namespace std;
typedef tuple<int, int, int> ti;
typedef pair<int, int> pi;
int n, m;
char mp[51][51];
int v[65][51][51];
int dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	queue<ti>q;
	int Y, X;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> mp[i][j];
			if (mp[i][j] == '0') {
				v[0][i][j] = 0;
				q.push({ i,j,0 });
			}
		}
	}
	int ans = INT_MAX, tempKeys;
	while (!q.empty()) {
		auto [y, x, k] = q.front(); q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
				if (!v[k][ny][nx] && mp[ny][nx] != '#') {
					if (mp[ny][nx]=='1') {
						ans = min(ans, v[k][y][x] + 1);
						continue;
					}
					else if ('A' <= mp[ny][nx] && mp[ny][nx] <= 'Z') {
						if (k & 1 << (mp[ny][nx] - 'A')) {
							v[k][ny][nx] = v[k][y][x] + 1;
							q.push({ ny,nx,k });
						}
					}
					else if ('a' <= mp[ny][nx] && mp[ny][nx] <= 'z') {
						if (!(k & 1 << (mp[ny][nx] - 'a'))) { //없는 열쇠를 얻으면 출발지점 push
							tempKeys = k;
							tempKeys |= (1 << (mp[ny][nx] - 'a'));
							v[tempKeys][ny][nx] = v[k][y][x] + 1;
							q.push({ ny,nx,tempKeys });
						}
						else {
							v[k][ny][nx] = v[k][y][x] + 1;
							q.push({ ny,nx,k });
						}
					}
					else {
						v[k][ny][nx] = v[k][y][x] + 1;  //열린 공간인경우
						q.push({ ny,nx ,k});
					}
				}
			}
		}
	}
	ans == INT_MAX ? cout << -1 : cout << ans;  //정답이 없으면 -1출력
}

방문을 표시하는 v배열이 3차원입니다.

v[k][y][x]는 좌표 Y,X에서 열쇠 K만큼 가지고 있을 때 방문을 확인합니다.

K는 비트마스크로 표현합니다.

 

만약 없는열쇠를 획득하면, tempKeys는 key|=획득키로,

v[key][ny][nx]가 아니라 v[tempKey][ny][nx]에 저장해 푸쉬합니다.