[BOJ 1194] 달이 차오른다, 가자.

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

bfs를 이용하여 문제를 해결하는 문제이다. 해당 문제를 풀때 고민해야하는 점이 있다면 어떤점을 이동할때 , 그리고 방문할때 다른 bfs처럼 visit 처리를 해주어야 하는데 그때마다 어떤 열쇠들을 가지고 있는지 그떄의 열쇠상태를 가지고 있어야 한다는 점이다. 

하지만 bfs특성상 while문 내에 키의 상태를 가지고 있는 배열 혹슨 백터들을 가지고 실행한다는 것은 메모리 초과로 이어지게 된다.

따라서 이러한 경우 필요한 테크닉은 비트마스크를 이용한 처리이다.

문제의 접근 핵심을 정리하자면 

(1) 열쇠는 6종류만 가지고 있다. 

(2) 어떤 지점을 방문할때 visit처리를 위해 visit배열의 선언을 visit[어떠한 열쇠를 가지고 있는지 비트정수][y좌표][x좌표] 형식으로 표현을 한다. 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>
#include <utility>
#include <set>
#include <tuple>
typedef long long ll;
 
#define INF 2e9
 
using namespace std;
 
int n,m,sy,sx,ans;
char arr[111][111];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
bool visit[1<<8][55][55];
 
bool chk(int y,int x){
    return 0<y && y<=n && 0<x && x<=m;
}
 
int bfs(int y, int x, int cnt,int key){
    
    queue<pair<pair<int,int>,pair<int,int>>> q;
    q.push({{y,x},{cnt,key}});
    
    while(!q.empty()){
        int yy = q.front().first.first;
        int xx = q.front().first.second;
        int cntt = q.front().second.first;
        int keyy = q.front().second.second;
        q.pop();
        
        if(arr[yy][xx] =='1'){
            ans = min(ans,cntt);
            continue;
        }
        
        for(int i=0;i<4;i++){
            int yyy = yy+dy[i];
            int xxx = xx+dx[i];
 
            if(chk(yyy,xxx)){
                if(arr[yyy][xxx] >='A' && arr[yyy][xxx] <='F' && !visit[keyy][yyy][xxx]){
                    if(keyy&(1<<(arr[yyy][xxx]-'A'+1))){
                        int t= keyy|(1<<(arr[yyy][xxx]-'A'+1));
                        q.push({{yyy,xxx},{cntt+1,t}});
                        visit[t][yyy][xxx] = true;
                    }
                    
                    continue;
                }
                
                if(arr[yyy][xxx] >='a' && arr[yyy][xxx] <='f'&& !visit[keyy][yyy][xxx]){
                    int t = keyy|(1<< (arr[yyy][xxx]-'a'+1));
                    q.push({{yyy,xxx},{cntt+1,t}});
                    visit[t][yyy][xxx] = true;
                    continue;
                }
                
                if(!visit[keyy][yyy][xxx] && arr[yyy][xxx] !='#'){
                    q.push({{yyy,xxx},{cntt+1,keyy}});
                    visit[keyy][yyy][xxx] = true;
                }
                
            }
        }
        
    }
    
    return ans;
    
}
 
int main(){
    memset(visit,false,sizeof(visit));
    ans = INF;
    scanf("%d%d" , &n,&m);
    for(int i=1;i<=n;i++){
        getchar();
        for(int j=1;j<=m;j++){
            scanf("%c" , &arr[i][j]);
            if(arr[i][j] == '0'){
                sy = i;
                sx = j;
            }
        }
    }
    int val = bfs(sy,sx,0,0);
    
    if(val == INF){
        printf("-1\n");
    }else{
        printf("%d\n",val);
    }
    return 0;
}

위의 코드에서 보이는것과 같이 visit배열을 [1<<8][55][55] 짜리로 선언하였다. 

이때 [1<<8] 의 의미는 총 8개의 열쇠상태를 표현하는것이고 ,(물론 문제에서는 6개만 사용그냥 늘려서 썻음;;) 

1<<1은 첫번째 비트를의미 , 1<<8 은 마지막은 8째 비트를 의미하는 것이다. 

이문제의 핵심 로직은 50~55번째 줄에서 해당 키가 있는지 확인하고, 있으면 들어가는 그런 방식이다. 

결론 -> bfs할떄 어떤 정보를 가지고 갈때 (메모리 초과로 이어질꺼 같을 때) 비트마스크를 이용해보자 . 끝