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

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

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

 

bfs 최단거리 문제임은 자명한데, 주어진 다른 조건이 있어 쉽지 않은 문제이다.

문제를 보며 깨달아야하는 것은 들고있는 열쇠마다 타일에 접근하는 것의 의미가 다름을 깨달아야한다.

 

즉 2,2 가  a라고 할 때 열쇠 a,b,c를 가지고 있는 것과 열쇠 a만을 가진 것은 의미가 전혀 다르다는 의미이다. 그래서 bfs를 돌 때 각 bfs 노드들은 x,y 말고도 현재 열쇠의 정보를 가지고 있어야한다. 

 

이 열쇠의 정보를 가지고 있는 것이 핵심이다. 열쇠의 정보를 어떻게 보관해야할까? vector를 이용하는 방법도 있을 것이고 배열을 이용하는 방법도 있겠지만 가장 유용한 방법은 비트마스킹이다.

 

만약 a 열쇠를 가지고 있다면 현재 비트마스킹 값은 000001 = 1

만약 c 열쇠를 가지고 있다면 현재 비트마스킹 값은 000100 = 4

a, c를 모두 가지고 있다면 현재 비트마스킹 값은 000101 = 5

 

비트마스킹의 가장 좋은 점은 아주 적은 매모리로 많은 경우의 수를 저장해놓을 수 있단거다. 

 

그렇다면 어떻께 비트마스킹을 관리해야할까?

 

만약 맨 처음, 알파뱃 'b' 를 만났다면 이렇게 될 것이다. 

현재 bitmasking = 000000

 

bitmasking = bitmasking | 1 << (board[][] - 'a') 

=> bitmasking = 000010

 

다음으로 d를 만난다면

 

000010 | 001000 => 001010

bitmasking = 001010 이다.

 

그리고 D를 만난다면 

 

bitmasking & 001000 = 001000 이 될 것이고 이는 0 이 아니므로 false가 아니다.

 

그러므로 bfs를 돌면서 다음과 같은 기준을 따른다.

 

1. 다음으로 소문자 알파뱃을 만나면 현재 bitmasking 과 or 연산으로 마스킹 업데이트

2. 그리고 다음 노드, 마스킹을 검사했을 때 방문하지 않았으면 방문

 

그러므로 방문배열은 visited[51][51][65] 가 필요하다. 왜 65냐면 위 알파뱃이 6개이기 때문에 비트마스킹은 총 2^6 = 64개를 모두 검사해야하므로 위와 같이 해야한다. 

 

시간 복잡도는 각 차원마다 각 타일을 1번씩 방문하는 것이 최악의 경우이므로 

 

TC = O(N * M * 64)

 

이다.

 

이 문제처럼 같은 타일을 방문하지만 하나의 차원을 더 두어서 다시 방문하여 체크하는 식으로 풀이하는 문제는 많다. 코딩테스트에도 충분히 난이도높게 출제될 수 있는 문제라고 본다.

 

관련 문제는 아기상어와 비슷하다고 생각된다. 

 

비슷한 문제

https://www.acmicpc.net/source/51117739

로그인

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int start_x, start_y;
bool visited[51][51][65] = { false, };
char board[51][51];

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		string tmp;
		cin >> tmp;
		for (int j = 0; j < M; j++) {
			board[i][j] = tmp[j];
			if (tmp[j] == '0') {
				start_x = i;
				start_y = j;
			}
		}
	}

	queue<pair<pair<int, int>, pair<int, int>>> q;

	q.push({ {start_x, start_y},{0,0} });

	int answer = -1;

	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int cnt = q.front().second.first;
		int bitmask = q.front().second.second;
		q.pop();

		visited[x][y][bitmask] = true;

		if (board[x][y] == '1') {
			answer = cnt;
			break;
		}

		//cout << cnt << endl;

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

			if (nx > -1 && nx < N && ny > -1 && ny < M) {
				int nextmask = bitmask;
				if ('a' <= board[nx][ny] && 'z' >= board[nx][ny]) {
					nextmask = bitmask | (1 << (int(board[nx][ny] - 'a')));
				}

				if (visited[nx][ny][nextmask] == true || board[nx][ny] == '#') continue;

				if ('A' <= board[nx][ny] && 'Z' >= board[nx][ny]) {
					if (nextmask & (1 << int(board[nx][ny] - 'A'))) {
						visited[nx][ny][nextmask] = true;
						q.push({ { nx, ny }, {cnt + 1, nextmask} });
					}
				}
				else {
					visited[nx][ny][nextmask] = true;
					q.push({ { nx, ny }, {cnt + 1, nextmask} });
				}
			}
		}
	}

	cout << answer << '\n';
}