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

link : https://www.acmicpc.net/problem/1018

달이 차오른다, 가자. 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3030	761	445	21.272%

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (소문자 a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (대문자 a - f)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (N,M <= 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

예제 입력 1 

1 7
f0.F..1

예제 출력 1 

7

BFS 문제이다. 조건 때문에 많은 경우의 수를 고려해주어야 한다. 모든 경우를 때려박으면(?) 쉽게 해결할 수 있다.

#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M;
char map[50][50];
 
priority_queue<pair<pair<int, int>, pair<int, int>>> minsick;
bool visited[1 << 6][51][51];
 
void solve();
 
int main() {
 
    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') {
                minsick.push({ { 0,0 },{ i, j } });
                map[i][j] = '.';
            }
        }
    }
 
    solve();
 
    return 0;
}
 
void solve() {
 
    int count;
    int key;
    int x, y;
    int temp_key;
 
    while (minsick.empty() != true) {
 
        count = minsick.top().first.first;
        key = minsick.top().first.second;
        x = minsick.top().second.first;
        y = minsick.top().second.second;
 
        //up
        if (x>0) {
            if (map[x - 1][y] == '.' && visited[key][x - 1][y] == false) {
                minsick.push({ { count - 1, key },{ x - 1, y } });
                visited[key][x - 1][y] = true;
            }
            else if (map[x - 1][y] >= 'a' && map[x - 1][y] <= 'f' && visited[key][x - 1][y] == false) {
                temp_key = key | (1 << (map[x - 1][y] - 'a'));
                minsick.push({ { count - 1, temp_key },{ x - 1, y } });
                visited[temp_key][x - 1][y] = true;
            }
            else if (map[x - 1][y] >= 'A' && map[x - 1][y] <= 'F' && visited[key][x - 1][y] == false) {
                if (key&(1 << (map[x - 1][y] - 'A'))) {
                    temp_key = key | (1 << (map[x - 1][y] - 'A'));
                    minsick.push({ { count - 1,temp_key },{ x - 1,y } });
                    visited[temp_key][x - 1][y] = true;
                }
            }
            else if (map[x - 1][y] == '1') {
                cout << -(count - 1);
                return;
            }
        }
 
        //down
        if (x<N - 1) {
            if (map[x + 1][y] == '.' && visited[key][x + 1][y] == false) {
                minsick.push({ { count - 1, key },{ x + 1, y } });
                visited[key][x + 1][y] = true;
            }
            else if (map[x + 1][y] >= 'a' && map[x + 1][y] <= 'f' && visited[key][x + 1][y] == false) {
                temp_key = key | (1 << (map[x + 1][y] - 'a'));
                minsick.push({ { count - 1, temp_key },{ x + 1, y } });
                visited[temp_key][x + 1][y] = true;
            }
            else if (map[x + 1][y] >= 'A' && map[x + 1][y] <= 'F' && visited[key][x + 1][y] == false) {
                if (key&(1 << (map[x + 1][y] - 'A'))) {
                    temp_key = key | (1 << (map[x + 1][y] - 'A'));
                    minsick.push({ { count - 1,temp_key },{ x + 1,y } });
                    visited[temp_key][x + 1][y] = true;
                }
            }
            else if (map[x + 1][y] == '1') {
                cout << -(count - 1);
                return;
            }
        }
 
        //left
        if (y>0) {
            if (map[x][y - 1] == '.' && visited[key][x][y - 1] == false) {
                minsick.push({ { count - 1, key },{ x, y - 1 } });
                visited[key][x][y - 1] = true;
            }
            else if (map[x][y - 1] >= 'a' && map[x][y - 1] <= 'f' && visited[key][x][y - 1] == false) {
                temp_key = key | (1 << (map[x][y - 1] - 'a'));
                minsick.push({ { count - 1, temp_key },{ x, y - 1 } });
                visited[temp_key][x][y - 1] = true;
            }
            else if (map[x][y - 1] >= 'A' && map[x][y - 1] <= 'F' && visited[key][x][y - 1] == false) {
                if (key&(1 << (map[x][y - 1] - 'A'))) {
                    temp_key = key | (1 << (map[x][y - 1] - 'A'));
                    minsick.push({ { count - 1,temp_key },{ x,y - 1 } });
                    visited[temp_key][x][y - 1] = true;
                }
            }
            else if (map[x][y - 1] == '1') {
                cout << -(count - 1);
                return;
            }
        }
 
        //right
        if (y<M - 1) {
            if (map[x][y + 1] == '.' && visited[key][x][y + 1] == false) {
                minsick.push({ { count - 1, key },{ x, y + 1 } });
                visited[key][x][y + 1] = true;
            }
            else if (map[x][y + 1] >= 'a' && map[x][y + 1] <= 'f' && visited[key][x][y + 1] == false) {
                temp_key = key | (1 << (map[x][y + 1] - 'a'));
                minsick.push({ { count - 1, temp_key },{ x, y + 1 } });
                visited[temp_key][x][y + 1] = true;
            }
            else if (map[x][y + 1] >= 'A' && map[x][y + 1] <= 'F' && visited[key][x][y + 1] == false) {
                if (key&(1 << (map[x][y + 1] - 'A'))) {
                    temp_key = key | (1 << (map[x][y + 1] - 'A'));
                    minsick.push({ { count - 1,temp_key },{ x,y + 1 } });
                    visited[temp_key][x][y + 1] = true;
                }
            }
            else if (map[x][y + 1] == '1') {
                cout << -(count - 1);
                return;
            }
        }
 
        minsick.pop();
    }
 
    cout << "-1";
}