[백준알고리즘] 1194번 달이 차오른다, 가자

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

한달 전에 풀었었다가 실패하고 다시 도전하였으나 또 실패..ㅠ

난 아직 문제에 맞는 효과적인 알고리즘을 찾아내는 것이 잘 안되는 것 같다..

<이 문제를 해결하기 위해 필요한 방법>

1. key를 줍는다 ==> | 연산

2. 문에 매칭되는 key가 있는지 확인한다 ==> & 연산

3. key가 갱신되었을 때는 왔던 길을 다시 갈 수 있다 ==> visited[][][]에 3차원으로 x,y,key값 넣기

나는 1번 2번까지는 했는데 3번을 하기 위해서 3차원 배열을 사용할 생각을 못하고 이전이랑 키값이 바뀌었을 때 변수를 두고 하려다 보니

이거야 원,,, 할 수가 없었다ㅋㅋㅋㅋㅋㅋㅋㅋ

그래서 결국 다른 사람들이 풀이한 것들을 참고하여 문제를 풀 수 있었다 ㅠㅠ

<문제를 푸는 방법>

bfs를 이용하여 미로를 탐색하고 비트마스킹을 통해 key를 줍고 현재 key를 확인한다.

미로를 탐색해나가며 처리해야할 조건.

1) 미로판의 범위를 벗어나지 않을 때에만 탐색

2) 벽이면 continue;

3) key이면 줍는다.

4) 문이면 매칭되는 key가 없을 때 continue;

5) 현재 key들을 가진 상태에서 방문했던 곳이면 continue;

(현재 key들을 가지고 있을 때 방문했던 곳이면 또 다시 방문할 필요가 없다. ==> 이러한 처리가 없으면 메모리초과가 된다)

6) 나머지 경우 ==> (갈 수 있는 곳 중에서 같은 key들을 가진 상태로 방문했던 적이 없을 때)

q에 현재 값을 넣는다.

현재 좌표, key를 방문했다고 표시한다.

(예시)

1 7

f0.F..1

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

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

    0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.
*/
 
#include<iostream>
#include<queue>
using namespace std;
 
int N, M, cnt;
bool flag;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
 
char miro[51][51]; // 미로
bool visited[51][51][64]; // x좌표, y좌표, key는 2*2*2*2*2*2=64 경우의 수, (0 에서 2^6-1 값) 까지 나올 수 있다. 0 ~ 63
queue<pair<pair<int, int>, int>>q; // x좌표, y좌표 key
 
int main()
{
    cin >> N >> M;
    char data = 0;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> data;
            miro[i][j] = data;
            if (miro[i][j] == '0') {
                q.push(make_pair(make_pair(i, j), 0));
                visited[i][j][0] = true;
            }
        }
    }
 
    while (!q.empty())
    {
        int size = q.size();
 
        while (size--)
        {
            int x = q.front().first.first;
            int y = q.front().first.second;
            int key = q.front().second;
            q.pop();
 
            if (miro[x][y] == '1')
            {
                flag = true;
                break;
            }
 
            for (int i = 0; i < 4; i++)
            {
                int mx = x + dx[i];
                int my = y + dy[i];
                int nkey = key;
 
                if (mx >= 0 && mx < N && my >= 0 && my < M)
                {
                    if (miro[mx][my] == '#') continue;
                    if (miro[mx][my] >= 'a' && miro[mx][my] <= 'f') nkey |= (1 << (miro[mx][my] - 'a'));
                    if (miro[mx][my] >= 'A' && miro[mx][my] <= 'F'){
                        if (!(nkey & (1 << (miro[mx][my] - 'A')))) continue;
                    }
                    if (visited[mx][my][nkey]) continue;
                    q.push(make_pair(make_pair(mx, my), nkey));
                    visited[mx][my][nkey] = true;
                }
            }
        }
        if (flag) break;
        else cnt++;
    }
 
    if (flag) cout << cnt;
    else cout << -1;
 
    return 0;
}