[백준] 1194 - 달이 차오른다, 가자.

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

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

 

보통 BFS라면, visit 같은 방문 배열에 체크를 해두고 다시는 방문하지 않는 것이 특징인데,

이러한 문제는 특정한 곳을 방문한 뒤에 다른 특정한 곳을 방문할 수 있다라는 것이 특이한 점이다.

 

문제를 잘 보면, N 제한은 50이고 열쇠는 최대 6개이다. 생각보다 제한이 작다.

BFS 문제에서 가장 고려해야 할 사항 중 하나는 바로 방문 배열을 어떻게 구성할 것인가 이다.

 

이 문제에서는 열쇠의 개수가 작으므로,

열쇠를 하나도 가지고 있지 않은 경우부터, 모든 열쇠를 가지고 있는 경우의 수를 모두 더해도 2 ^ 6 = 64 밖에 되지 않는다.

따라서 이 점을 이용할 것이다.

 

visit[a][b][c] = c의 조합으로 a행 b열을 방문

즉, c = 0이라면 열쇠를 하나도 가지고 있지 않은 상태에서 방문한다는 뜻이고,

c = 63이라면 모든 열쇠를 가지고 방문한다는 뜻이다.

 

구현은 비트마스킹으로 생각보다 쉽게 구현할 수 있었다.

 

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

int n, m;
char map[50][50];
int visit[50][50][64];
int x[4] = { 0,0,1,-1 };
int y[4] = { 1,-1,0,0 };
queue<tuple<int, int, int>> q;

int main() {

	cin >> n >> m;
    
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == '0') {
				q.push({ i,j,0 });
				visit[i][j][0] = 1;
			}
		}
	}
    
	while (!q.empty()) {
    
		int a, b, c;
		tie(a, b, c) = q.front();
		q.pop();

		if (map[a][b] == '1') {
			cout << visit[a][b][c] - 1;
			return 0;
		}

		for (int k = 0; k < 4; k++) {
			int nx = a + x[k];
			int ny = b + y[k];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (map[nx][ny] != '#') {
					if (map[nx][ny] >= 'a' && map[nx][ny] <= 'z') {
						if (!visit[nx][ny][c | (1 << (map[nx][ny] - 'a'))]) {
							q.push({ nx,ny,c | (1 << (map[nx][ny] - 'a')) });
							visit[nx][ny][c | (1 << (map[nx][ny] - 'a'))] = visit[a][b][c] + 1;
						}
					}
					else if (map[nx][ny] >= 'A' && map[nx][ny] <= 'Z') {
						if (c & (1 << (map[nx][ny] - 'A')) && !visit[nx][ny][c]) {
							q.push({ nx,ny,c });
							visit[nx][ny][c] = visit[a][b][c] + 1;
						}
					}
					else { // 출구
						if (!visit[nx][ny][c]) {
							q.push({ nx,ny,c });
							visit[nx][ny][c] = visit[a][b][c] + 1;
						}
					}
				}
			}
		}
	}
    
	cout << -1;
}