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

문제

https://www.acmicpc.net/problem/1194

0에서 출발하여 1까지 갈 수 있는 최단경로를 구하는 문제이다. 

#은 지나갈 수 없고, a~f는 열쇠, A~F는 문이며 각 문을 지나기 위해서는 해당하는 소문자 열쇠를 가지고 있어야한다. 

풀이

열쇠와 문이라는 요소가 추가되기는 했지만, 기본적으로는 BFS를 이용하여 최단경로를 찾는 문제이다. 

구조체를 만들어서 BFS를 돌리는것 까지는 비교적으로 금방 할 수 있었는데, 메모리초과가 났다. 

 

visited배열을 visited[2][2][2][2][2][2][51][51]로 만들고, 구조체에 6칸짜리 vector를 넣어서 그런 것 같았다. 

 

검색을 해보니, 열쇠 관련 부분을 "비트마스킹"으로 해결해야 하는 문제였다. 

따라서 visited배열을 visited[51][51][64] 로 바꾸고, 구조체에 key관련 변수를 그냥 int로 바꿨더니 통과되었다. 

* key가 a~f까지 6종류이기 때문에, 111111(2) = 63이다. 따라서 key가지수는 0~63의 64가지 이다. 

 

열쇠를 얻을때는 | (OR) 연산을 이용해 key에 해당 열쇠를 추가하였고, 

문을 열 때는 & (AND) 연산을 이용해서 해당 열쇠가 존재하는지 확인하였다. 

 

1 << 1 : a열쇠

1 << 2 : b열쇠

1 << 3 : c열쇠

1 << 4 : d열쇠

1 << 5 : e열쇠

1 << 6 : f열쇠

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int N, M;
char map[51][51];
bool visited[51][51][1 << 6] = { 0, }; //1 << 6 -> 2진수 111111 -> 64

int dn[4] = { -1,1,0,0 };
int dm[4] = { 0,0,-1,1 };
struct Node {
	int n;
	int m;
	int count;
	int keys;
};
int BFS(int startN, int startM) {
	queue<Node> q;
	q.push({ startN, startM, 0, 0 });
	visited[startN][startM][0] = 1;

	while (!q.empty()) {
		int tempN = q.front().n;
		int tempM = q.front().m;
		int count = q.front().count;
		int keys = q.front().keys;
		q.pop();
		
		for (int i = 0;i < 4;i++) {
			int nextN = tempN + dn[i];
			int nextM = tempM + dm[i];

			if (nextN < 0 || nextN >= N || nextM < 0 || nextM >= M) continue;

			if (map[nextN][nextM] == '#') continue; //벽
		
			if (!visited[nextN][nextM][keys]) {
				if (map[nextN][nextM] == '1') // 출구 
					return count + 1;
				if (map[nextN][nextM] >= 'a' && map[nextN][nextM] <= 'f') { // 열쇠 
					int newkeys = keys | (1 << (int)(map[nextN][nextM] - 'a'));
					visited[nextN][nextM][newkeys] = 1;
					q.push({ nextN, nextM, count + 1, newkeys });
				}
				else if (map[nextN][nextM] >= 'A' && map[nextN][nextM] <= 'F') { // 문
					if ((keys & (1 << (int)(map[nextN][nextM] - 'A'))) == 0) continue;
					q.push({ nextN, nextM, count + 1, keys });
					visited[nextN][nextM][keys] = 1;
				}
				else { // 빈 곳, 출발지 재 방문
					q.push({ nextN, nextM, count + 1, keys });
					visited[nextN][nextM][keys] = 1;
				}
			}
		}
	}
	return -1;
}
int main(void) {
	cin >> N >> M;
	int startN, startM;
	for (int n = 0;n < N;n++) {
		for (int m = 0;m < M;m++) {
			cin >> map[n][m];
			if (map[n][m] == '0') {
				startN = n;
				startM = m;
			}
		}
	}

	int result = BFS(startN, startM);
	cout << result << endl;
	return 0;
}

결과

참고

비트마스크 아이디어를 얻을 수 있었다 !

https://j2wooooo.tistory.com/39