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

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

코드

#include <iostream>
#include <queue>
using namespace std;

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);

#define MAX 51
int n, m, x, y;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
char arr[MAX][MAX];
bool visit[MAX][MAX][1 << 6];

typedef struct {
	int x;
	int y;
	int key;
	int cnt;
} p;

int bfs() {
	queue<p> q;
	q.push({x, y, 0, 0});
	visit[x][y][0] = true;

	while (!q.empty()) {
		int nx = q.front().x;
		int ny = q.front().y;
		int key = q.front().key;
		int cnt = q.front().cnt;
		q.pop();

		if (arr[nx][ny] == '1') return cnt;

		for (int i = 0; i < 4; i++) {
			int gx = nx + dx[i];
			int gy = ny + dy[i];

			if (gx >= 0 && gx < n && gy >= 0 && gy < m && arr[gx][gy] != '#' && !visit[gx][gy][key]) {
				int newKey = key;
				if (arr[gx][gy] >= 'a' && arr[gx][gy] <= 'f') 
					newKey |= (1 << (arr[gx][gy] - 'a'));
				else if (arr[gx][gy] >= 'A' && arr[gx][gy] <= 'F') 
				{
					if (!(key & (1 << (arr[gx][gy] - 'A')))) 
						continue;
				}

				if (!visit[gx][gy][newKey]) {
					visit[gx][gy][newKey] = true;
					q.push({ gx, gy, newKey, cnt + 1 });
				}
			}
		}
	}
	return -1;
}

int main() {
	FASTIO;

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == '0') {
				x = i;
				y = j;
			}
		}
	}

	cout << bfs();
	return 0;
}

코드 설명

기본적인 BFS에 열쇠 관리만 잘 하면 되는 문제이다. 이때 비트마스킹을 이용해 열쇠를 관리한다.

 

메인함수에서 미로에 대한 정보를 받고 민식의 현재 위치를 기록한다. 이후 bfs 함수를 호출하고 리턴되는 값(탈출하는데 걸리는 이동 횟수의 최솟값, 탈출 불가 시 -1)을 출력하면 된다.

 

bfs 함수 내에서 사용해야 하는 값은 크게 4개다. 현재 위치의 x좌표, y좌표, 이동 횟수, 현재 위치까지 오면서 가지고 있는 열쇠 정보이다. pair<int, int> 형태로 사용하다가 헷갈릴 수 있을 것 같아서 구조체를 만들었다. visit 배열은 3차원으로 관리한다. (x, y, key) 큐를 돌면서 내부 for문을 통해 갈 수 있는 칸을 확인한다. 열쇠를 주우면 newKey의 값을 갱신한다. 문을 만났지만 대응하는 키가 없을 경우에는 continue한다.

 

현재 정보를 가진 채 방문하지 않은 칸일 경우에만 큐에 해당 정보를 넣어준다.

 

느낀 점

비트마스킹을 모를 때 도전했다가 열쇠 관리를 실패해서 비트마스킹을 공부하고 풀어야겠다고 생각했던 문제다. 이번 여름방학 때 ALGOS에서 비트마스킹을 공부하고 다시 도전했다! 구현 자체는 빠르게 했는데,  visit 배열 관리를 잘못 해서 예제가 몇 개 통과하지 못했다.. 배열 관리를 고쳐주고 제출하니 한 번에 맞았다!