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

이 문제는 BFS 를 이용해 푸는 미로 문제의 응용버전이라고 볼 수 있다.

이 문제만의 특징은 'A'~'F' 의 문이 있고, 문을 열기 위해선 각 알파벳에 맞는 소문자 'a'~'f' 열쇠를 가지고 있으면 통과할 수 있다.

 

다행히 문과 열쇠의 종류가 6개 밖에 안되기 때문에, 비트마스크를 이용해 저장할 수 있고

주의할 점은 지나온 길을 다시 가지 않기 위한 visited 변수는 키의 보유 상황에 따라 갈 수 있는 길이 다르기 때문에 이를 고려해야한다.

 

 

 

 

 소스코드

 

#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
 
int n,m, sy,sx, dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
char map[55][55];
int visited[55][55][66];
 
struct cell {
    int y, x, step, keys;    
    cell(int y, int x, int step, int keys) : y(y), x(x), step(step), keys(keys) { }
};
 
bool check_next_step(int y,int x, int keys){
    if (map[y][x] >= 'A' && map[y][x] <= 'F'){
        return keys & (1<<map[y][x] - 'A');
    } else {
        return map[y][x] != '#';
    }
}
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%s",map[i]);
        for(int j=0;j<m;j++){
            if(map[i][j] == '0'){
                sy=i, sx=j;
            }
        }
    }
    queue < cell > q;
    q.push(cell(sy,sx, 0, 0));
    visited[sy][sx][0] = true;
    int ans = -1;
    while(!q.empty()){
        cell cur = q.front(); q.pop();        
        if(map[cur.y][cur.x] == '1') {
            ans = cur.step;
            break;
        }
        if (map[cur.y][cur.x] >='a' && map[cur.y][cur.x] <='f') {
            cur.keys |= (1<< (map[cur.y][cur.x] - 'a'));
        }        
        for(int i=0;i<4;i++){
            int ny = cur.y + dy[i], nx = cur.x + dx[i];
            if(nx>=0 && ny >=0 && nx < m && ny < n && !visited[ny][nx][cur.keys]){
                if(check_next_step(ny,nx, cur.keys)) {
                    visited[ny][nx][cur.keys] = true;
                    q.push(cell(ny, nx, cur.step+1, cur.keys));
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}