문제링크

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

문제

풀이

BFS + 비트마스킹 문제이다.

문제의 핵심은 다음과 같다.

1. 비트마스킹을 이용한 열쇠 보유 여부 체크

열쇠를 가지고 있는지 여부에 따라 방문이 가능한지 결정되기 때문에 비트마스킹을 통해 열쇠를 가지고 있는지 체크해 주었다.

ex 1 ) 열쇠 얻기

현재 a와 d 키를 보유하고 있다고 가정하고 다음에 방문하는 지역에 있는 열쇠 f가 있다면 비트연산( | ) 을 통해 열쇠를 얻을 수 있다 .

key : fedcba

now : 001001 (9)
     f : 100000 (32)
===============
         101001 (41)

즉, now = now | f 를 통해 열쇠를 얻을 수 있다.

ex 2) 열쇠 보유 여부

현재 c와 d키를 보유하고 있다고 가정하고 다음에 방문하는 지역에 문 C가 있다면 비트연산 ( & ) 를 통해 방문 가능 여부를 체크할 수 있다.

key : fedcba

now : 001100 ( 12 )
    C : 000100 ( 4 )
===============
        000100

즉, key & C == C 가 true 인 경우 방문이 가능하다

2. visit 배열을 통한 방문여부 체크

단순히 방문을 했는지 체크하는게 아니라 어떤 열쇠를 가진 상태에서 어느 위치에 방문했는지를 체크해야 한다. ( 비슷한 유형으로 BOJ 2206 벽부수고 이동하기 문제를 풀어보면 도움이 된다.)

열쇠의 종류는 a~f의 6가지 이므로 6비트를 사용한다.
따라서 최대값이 2^6 -1 = 63 이므로 배열은 visit[51][51][64] 로 선언하고 방문 여부를 표시해 주었다.

코드

#include <iostream>
#include <queue>
using namespace std;
typedef struct pos {
	int x, y, key;
};

int n, m;
int days;
char maps[51][51];
bool vi[51][51][64];
int dx[4]{ 0,0,1,-1 };
int dy[4]{ 1,-1,0,0 };
queue<pos> q;

int bfs() {

	while (!q.empty()) {
		int sz = q.size();
		for (int i = 0; i < sz; i++) {
			int x = q.front().x;
			int y = q.front().y;
			int key = q.front().key;
			q.pop();

			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;

				if (maps[nx][ny] == '.') {
					if (!vi[nx][ny][key]) {
						vi[nx][ny][key] = true;
						q.push({ nx,ny,key });
					}
				}
				else if ('a' <= maps[nx][ny] && maps[nx][ny] <= 'f') {
					int temp_key = 1;
					temp_key <<= (maps[nx][ny] - 'a');
					int nkey = key | temp_key;
					if (!vi[nx][ny][nkey]) {
						vi[nx][ny][nkey] = true;
						q.push({ nx,ny,nkey });
					}
				}
				else if ('A' <= maps[nx][ny] && maps[nx][ny] <= 'F') {
					int temp_key = 1;
					temp_key <<= (maps[nx][ny] - 'A');
					if ( ( (temp_key & key) == temp_key ) && !vi[nx][ny][key]) {
						vi[nx][ny][key] = true;
						q.push({ nx,ny,key });
					}//열쇠 있는 경우
				}
				else if(maps[nx][ny]=='1'){
					return days+1;
				}

			}//for j
		}//for i 
		days++;
	}//while(!q.empty())
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maps[i][j];
			if (maps[i][j] == '0') {
				vi[i][j][0] = true;
				maps[i][j] = '.';
				q.push({ i,j,0 });
			}
		}
	}
	cout << bfs();
}

후기

비트마스킹의 개념에 대해 익히기 너무 좋은 문제라고 생각한다.
비트마스킹 문제를 푼 경험이 많이 없었는데 좋은 연습이 됐다.