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

문제 요약

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오. 미로는 빈 칸과 벽, 열쇠, 문, 현재 위치, 출구 위치가 주어진다. 문을 지나가기 위해서는 그에 대응하는 열쇠가 필요하다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• 비트마스킹

문제 풀이

BFS로 탐색하는 문제인데, 열쇠의 소지 유무가 들어간 문제이다. 왔던 경로를 탐색하더라도 소지한 열쇠가 다르다면 아예 다른 경로로 파악해야 하므로 visited배열은 key가 들어간 3차원 배열이어야 할 것이다.

기본적인 BFS에서 소지한 키의 유무를 비트마스킹으로 표현한 변수가 더 필요하다. 즉, 현재 소지한 키의 변수를 key라고 한다면, key |= 1 << (ary[nexty][nextx] - 'a')의 식이 될 것이다. 이렇게 하면, ary[nexty][nextx]를 탐색할 때 해당 값이 a~f일 때, a는 1번 비트를, b는 2번 비트를... 이런식으로 f가 6번 비트를 1로 만들 것이다.

key를 갱신하여 탐색하는 부분에서 잘못한다면, 시간초과가 난다. 현재 갖고있는 키를 먼저 갱신을 하고, visited배열을 검사한 뒤, 큐에 넣어주면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

bool visited[50][50][1 << 6];
short dir[4][2] = { {0,1}, {0,-1}, {1,0},{-1,0} };

int main()
{
	queue<pair<pair<int, int>,int>> q;
	short n, m, x, y, key, qsize, level = -1;
	char ary[50][50];
	bool sol = false;
	cin >> n >> m;
	getchar();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%c", &ary[i][j]);
			if (ary[i][j] == '0') {
				x = j;
				y = i;
			}
		}
		getchar();
	}
	q.push({ {x, y}, 0 });
	while (!q.empty()) {
		qsize = q.size();
		level++;
		while (qsize--) {
			x = q.front().first.first;
			y = q.front().first.second;
			key = q.front().second;
			visited[y][x][key] = true;
			q.pop();
			if (ary[y][x] == '1') {
				sol = true;
				break;
			}
			for (int i = 0; i < 4; i++) {
				int nextx = x + dir[i][1];
				int nexty = y + dir[i][0];

				if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
					int nextkey = key;
					if (ary[nexty][nextx] == '#') continue;
					if (ary[nexty][nextx] >= 'a' && ary[nexty][nextx] <= 'f')
						nextkey |= 1 << (ary[nexty][nextx] - 'a');
					else if (ary[nexty][nextx] >= 'A' && ary[nexty][nextx] <= 'F') {
						if (!(key & (1 << (ary[nexty][nextx] - 'A')))) continue;
					}
					if (!visited[nexty][nextx][nextkey]) {
						visited[nexty][nextx][nextkey] = true;
						q.push({ {nextx, nexty}, nextkey });
					}
				}
			}
		}
		if (sol) break;
	}
	if (sol) cout << level;
	else cout << -1;
	return 0;
}