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

문제

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

위 조건에 따라 키를 찾고 문을 따고를 반복해 미로를 탈출하면 되는 문제입니다.

저는 이 문제를 BFS와 재귀를 이용해 풀었는데, 처음에 문제를 자세히 읽지 않아 키값으로 알파벳(a~z)을 모두 활용하는 줄 알고 배열에서 비트 마스크를 사용하면 2^26으로 메모리 초과가 뜨겠구나 생각했었습니다..

문제에서는 알파벳(a~f)만 활용하니 비트 마스크를 사용해도 문제가 되지 않습니다!

비트 마스크를 활용하면 굳이 재귀를 사용하지 않고도, 3차원 방문 배열로 풀이할 수 있어 불필요한 탐색을 줄일 수 있습니다.

다른 분들 풀이를 보니 전부 비트 마스크를 활용해 풀이하셔서 이런 풀이도 있구나 참고만 하시면 될 것 같습니다!

알고리즘

알고리즘은 다음과 같습니다.

1. 출발점에서 BFS 탐색을 시작합니다.
   • 만약 키를 발견 시
     - 키를 이미 소지하고 있다면 큐에 그냥 좌표만 삽입합니다.
     - 키가 없다면 해당 키를 true로 설정한 뒤, (해당 좌표, 현재까지 이동 횟수)를 시작으로 삼아 다시 BFS를 재귀 호출합니다.
     - 재귀 호출을 마치면, 다시 해당 키를 false로 설정합니다.
     
     
   • 만약 문을 발견 시
     - 키를 이미 소지하고 있다면 큐에 그냥 좌표만 삽입합니다.
     - 키가 없다면 무시합니다.
     
     
   • 만약 목적지 발견 시
     - 현재까지 이동 횟수가 result 변수보다 작다면 갱신시킵니다.
     
     
   • 만약 빈공간 발견 시
     - 큐에 그냥 좌표만 삽입합니다.
     
     
2. bfs 연산이 끝나고, result 변수가 초기값 그대로라면 -1을 출력하고, 갱신되었다면 result 변수를 출력합니다.

문제 예제 3번에 위 알고리즘을 적용시키면 아래와 같습니다.

• 동그라미친 부분(Key)에서 BFS 재귀가 수행되고, 색이 바뀌어 다시 탐색을 시작합니다.

• 빨간색이 1번째, 파란색이 2번째, 보라색이 3번째, 노란색이 4번째 BFS를 보여줍니다.
  (중간중간 생략된 부분이 있으며, 길어져서 중간에 끊었습니다)

소스코드

#include<bits/stdc++.h>
using namespace std;
#define MAXN 51
#define t tuple<int, int, int>

int n, m, result = INT_MAX, dir[2][4] = { {-1, 1, 0, 0}, {0, 0, -1, 1}};
char maze[MAXN][MAXN];
bool keys[26];

bool check_range(int y, int x) {
	if (y < n && x < m && y >= 0 && x >= 0) return true;
	return false;
}

void bfs(t start) {
	int y, x, time;
	tie(y, x, time) = start;
	bool visited[MAXN][MAXN] = {false, };
	queue<t> q;
	q.push(start);
	visited[y][x] = true;

	while (q.size()) {
		int cy, cx, ctime;
		tie(cy, cx, ctime) = q.front(); q.pop();

		if (result != INT_MAX && ctime > result) break;

		for (int i = 0; i < 4; i++) {
			int ny = cy + dir[0][i], nx = cx + dir[1][i];

			if (check_range(ny, nx) && !visited[ny][nx]) {

				// 다음 위치가 목적지라면
				if (maze[ny][nx] == '1' && ctime + 1 < result) {
					result = ctime + 1;
					return;
				}

				// 다음 위치가 빈 공간이라면
				else if (maze[ny][nx] == '.' || maze[ny][nx] == '0') {
					q.push({ ny, nx, ctime + 1 });
				}

				// 다음 위치가 키라면
				else if (maze[ny][nx] >= 'a' && maze[ny][nx] <= 'z') {

					// 키를 이미 가지고 있다면
					if (keys[maze[ny][nx] - 'a']) {
						q.push({ ny, nx, ctime + 1 });
					}
					// 키가 없다면
					else {
						keys[maze[ny][nx] - 'a'] = true;
						bfs({ ny, nx, ctime + 1 });
						keys[maze[ny][nx] - 'a'] = false;
					}
				}

				// 다음 위치가 문이라면
				else if (maze[ny][nx] >= 'A' && maze[ny][nx] <= 'Z') {
					// 키를 가지고 있다면
					if (keys[maze[ny][nx] - 'A']) {
						q.push({ ny, nx, ctime + 1 });
					}
					// 키가 없다면
					else {
						continue;
					}
				}

				visited[ny][nx] = true;
			}
		}
	}
}

int main() {
	cin >> n >> m;

	t start;

	for (int i = 0; i < n; i++) {
		for (int k = 0; k < m; k++) {
			cin >> maze[i][k];
			if (maze[i][k] == '0') {
				start = make_tuple(i, k, 0);
			}
		}
	}

	bfs(start);

	if (result != INT_MAX) {
		cout << result;
	}
	else {
		cout << "-1";
	}
}

• BFS는 각각 다른 세계(?)에서 탐색해야 되므로 큐와 방문 배열은 지역 변수로 선언해주었습니다.

• key 배열은 재귀 호출이 끝나면 다시 원상태로 복귀해주었습니다.

확실히 다른 풀이보다 시간을 더 많이 잡아먹습니다.