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

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

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

#include<stdio.h>
#include<queue>
#define NSIZE 50
#define MSIZE 50
using namespace std;
int N, M;
char input[NSIZE][MSIZE];
int chk[NSIZE][MSIZE][64];
int dy[] = { 0,1,0,-1 };
int dx[] = { 1,0,-1,0 };
struct Data {
    int y, x, cnt, key;
};
queue<Data>q;
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf(" %1c", &input[i][j]);
            if (input[i][j] == '0') {
                q.push({ i,j,0,0 });
                chk[i][j][0] = 1;
            }
        }
    }
}
void bfs() {
    while (!q.empty()) {
        Data c = q.front(); q.pop();
        if (input[c.y][c.x] == '1') {// 탈출 가능
            printf("%d\n", c.cnt);
            return;
        }
        for (int dir = 0; dir < 4; dir++) {
            Data n;
            n.y = c.y + dy[dir];
            n.x = c.x + dx[dir];
            n.cnt = c.cnt + 1;
            n.key = c.key;
            if (0 <= n.y&&n.y < N && 0 <= n.x&&n.x < M) {
                if (chk[n.y][n.x][n.key] == 0 && input[n.y][n.x] != '#') {
                    chk[n.y][n.x][n.key] = 1;
                    if ('A' <= input[n.y][n.x] && input[n.y][n.x] <= 'F') {
                        if (n.key & 1 << input[n.y][n.x] - 'A') {//키가 있는경우
                            q.push(n);
                        }        
                    }
                    else if ('a' <= input[n.y][n.x] && input[n.y][n.x] <= 'f') {
                        n.key = n.key | 1 << input[n.y][n.x] - 'a';
                        
                        q.push(n);
                    }
                    else {
                        q.push(n);
                    }
                }
            }
        }
    }
    printf("-1\n");
}
int main(void) {
    init();
    bfs();
    return 0;
}

비트로 연산을 하더라도 키를 전부 가지고 있을떄의 정수는 63이므로 배열을 

이렇게 지정을 해주었고

위와 같이 키를 가지게 할때는 OR 연산자인 |  이걸로 하고 

문을 열수 있는 열쇠가 있는지 확인 하기 위해서 는 &  AND 연산자로 해주어야 키로 문을 열수 있습니다.

왜냐하면 

이 식이 문을 열수 있는 지 없는지 확인 하는 경우 인데

우선 키가 f만 가지고 있으면 현재 

 n.key는 1 0 0 0 0 0 비트이므로 32를 현재 n.key 가 가지고 있고 

현제 inpt[n.y][n.x]==F 라면 1<< 시프트 했을때 1 0 0 0 0 0 이므로

1 0 0 0 0 0

1 0 0 0 0 0

를 AND 연산 해주면 1 이기때문에 참이 됨으로 큐에 문이 열렸으니 넣을 수 있는 것입니다.

AND 연산은 

0 0 1

0 1 0

1 0 0

1 1 1

이라는 조건을 가지고 있기때문입니다. 무슨 소리냐 하시는 분들은  & 와 | 연산하는법을 참조해주시면

도움이 많이 될듯 합니다. 이렇게만해서 키가 있으면 문을 열고 그위치를 큐에 넣기만 하면 알아서 하기떄문에 

그냥 bfs와 별 다를바 없어지죠?

저도 처음에는 이해를 못한것은 아니지만 그냥 안하다보니 하기 싫었는데  진짜 해보니 별거 아니더라구요.

여러분들은 더 똑똑하시고 잘하시니까 더 잘 이해하고 잘하실꺼라 생각합니다.

오늘은 여기까지이고 다음주도 좋은 자료가지고 돌아오겠습니다. 이상 입니다.