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

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

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

신박한데 재밌는문제.. 일단 최소거리이므로 bfs로 탐색해준다. 그리고 6개의 키가 있고 다차원배열로 방문여부를 생각해줘야겠다는 생각을 했다. 

어려웠던 점은 각 키들의 조합수 대로 배열이 있어야된다는 것이었고 비트마스크라는 개념을 알게되었다. 이진수를 이용하여 000000를 통해 a~f의 키 조합을 표현하는게 간편했다. 111111 = 2^6 - 1 = (1<<6) - 1 =63 가 최대 크기이다.

**참고

https://m.blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221150706030&proxyReferer=https%3A%2F%2Fwww.google.com%2F

비트마스크(bit mask)

 

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
struct INFO {
    int r, c, k;
};
 
int N, M, r, c;
char map[50][50];
int isV[50][50][64]; //abcdef 
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
queue<INFO> q;
 
void solve() {
    while (!q.empty()) {
        int nr = q.front().r, nc = q.front().c, nk = q.front().k; q.pop();
        for (int i = 0; i < 4; i++) {
            int nrr = nr + dr[i], ncc = nc + dc[i], nkk = nk;
            if (nrr < 0 || ncc < 0 || nrr >= N || ncc >= M || isV[nrr][ncc][nkk] != 0 || map[nrr][ncc] == '#') continue;
            if ('a' <= map[nrr][ncc] && map[nrr][ncc] <= 'f') {
                nkk |= (1 << map[nrr][ncc] - 'a'); //열쇠 추가
            }
            else if ('A' <= map[nrr][ncc] && map[nrr][ncc] <= 'F') {
                if (!(nkk & (1 << map[nrr][ncc] - 'A'))) continue; //열쇠 없으면 패스
            }
            q.push({ nrr,ncc,nkk });
            isV[nrr][ncc][nkk] = isV[nr][nc][nk] + 1;
            if (map[nrr][ncc] == '1') {
                printf("%d\n", isV[nrr][ncc][nkk]);
                return;
            }
        }
    }
    printf("-1\n");
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    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') r = i, c = j; }
    q.push({ r,c ,0 });
    solve();
    return 0;
}