[ 백준 1194 ] 달이 차오른다, 가자. (C++)

백준의 달이 차오른다, 가자(1194) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 먼저, 본인은 비트마스크를 굉장히 싫어하고 할 줄도 모른다. 너무 어려운 내용이기도 하고 딱히 비트마스크를 모르더라도

   많은 문제를 해결했었기 때문이다. 하지만.... 이 문제만큼은 비트마스크를 사용했다.

   비트마스크를 할 줄 모르더라도, 그리 어려운 개념이 아니니 이 문제를 통해서 이런식으로 구현하는 구나 정도만 알고가자 !

  

   먼저 비트마스크가 뭔지 알아보자. 말 그대로 우리가 관리하고자 하는 값을 비트(2진수) 로 나타내어서 관리를 하는 것이다.

   그렇다면, 모두가 알고 있는 내용이겠지만 한번 만 더 되새기고 가보자.

   OR 연산의 기호는 | 이다. AND연산의 기호는 & 이다.

   OR는 두 개의 비트를 연산했을 때, 1개만 참이면 참을, AND는 2개 모두 참일 때만 참을 반환하는 연산 기호이다.

   뭐 비트마스크가 이런거다... 정말 이정도만 알아도 이 문제는 해결할 수 있다.

   아 그리고, 참고적으로 말하자면 우리는 진짜 2진수를 사용하는 것이 아니라, 단지 int형의 숫자들을 비트'처럼' 사용할

   뿐이다. 이 말을 하는 이유는 이제부터 읽을 내용에서 참을 반환하다, 거짓을 반환하다 이런 말들이 많을 텐데

   실제 2진수에서는 그게 맞는말이지만, 우리는 int형 변수들을 비트처럼 사용하는 것이기 때문에 0이 아니면 모두

   참을 반환한다고 생각해야 한다.

 

   그렇다면, 이 문제에서 왜 비트마스크 비트마스크 하는지 그 이유부터 알고 시작하자.

   먼저 소문자로 열쇠가 주어진다.(a ~ f). 이 열쇠로는 대문자 문을(A ~ F) 열 수가 있다.

   A ~ F , 총 6개의 상태를 비트로 나타내면 굉장히 편하기 때문이다. 무슨 개소리인지 모르겠다. 나도 그렇다.

   우리가 가질 수 있는 총 6개의 열쇠를 가졌냐 안가졌냐를 비트로 표현하는 것이다.

   000000 이렇게 ! 만약에, 이 중에서 열쇠 a를 주웠다 ? 그러면 000000 → 000001이 되는 것이다.

   저 상태에서 d랑 f를 주웠다 ? 그러면 000001 → 101001 이런식으로 표현을 하기 위함이다.

   열쇠를 가졌냐 안가졌냐를 단지 저렇게 표현하기 위해서 비트마스크를 사용한 것이다.

   그렇다면, 문을 만나게 되면 어떻게해야할까??

   우리는 현재 열쇠 a를 주운 상태이고, 문 'A' 를 만났다고 가정해보자. ( 그렇다면 우리는 이 문을 열 수 있겠지? )

   이 문을 열 수 있는지 없는지를 숫자 '1'과 '0' 2개로 어떻게 해야 판단할 수 있을까?

   좀 더 구체적으로 질문을 바꿔보자면, 우리의 현재 열쇠 상태인 000001 로 문 A를 어떻게 해야지 '참'의 결과를 가져올 수

   있을까??

   바로 정답은 & 연산이다. 근데... 뭐랑 뭐를 & 연산을 해야되?? 그 부분을 알아보자.

   위에서 말한대로라면 000001 & ??? = 1(참) 이렇게 되어야 한다는 말이다.

   비트마스크에서 가장 많이 사용되는 방식이 Shift연산이다. Shift연산은 비트를 왼쪽 혹은 오른쪽으로 옮기는 연산을

   의미한다. 그 중에서 가장 많이 쓰이는 방식이 1을 Shift 시켜버리는 연산을 많이 사용한다.

  

   자, 우리는 이제 위에 밑줄 그은 ??? 를 찾아야 하고, 1을 Shift연산해서 뭐 어떻게 함 써봐라 정도를 알고 있다.

   000001 & ??? = 1(참)

   ??? 에 들어갈 내용은 000001일 것이다.

   000001 & 000001 = 1 이기 때문이다. 그래 여기까지만 하고 여기서 갑자기 문제를 한번 바꿔보자.

   기존상태에서 우리는, 열쇠 d를 주웠고 우리는 D문을 만났다고 생각해보자.

   그럼 우리의 열쇠상태는?? 001001 이 될것이다. 문 D를 만났지만 우리는 열쇠를 가지고 있으므로 문을 열수가 있다.

   즉 & 연산을 통해서 또 '참'의 결과를 얻어야 한다.

   어떻게 해야할까??

   001001 과 001000을 & 연산을 하면 참이 나올 것이다. 사실 문제를 갑자기 바꾼것이 아니다. 비교를 하기 위해서 그런거지 !

  

   - A문을 만났을 때 → 000001 과 &연산

   - D문을 만났을 때 → 001000 과 &연산

   위의 결과를 Shift연산을 통해서 말하자면, A문을 만났을 때는 1을 0칸 Shift한 값과 & 연산을, D문을 만났을 때는 1을 3칸

   Shift한 값과 & 연산을 진행하였다.

   느낌이 오지 않는가 ?! A는 알파벳을 Index화 시켰을 때 0번이고, D는 3번이다 ! 딱 이정도만 알고 조금 있다가 더 구체적으

   로 확실하게 알아보자 !

   사실 우리가 하나 그냥 넘어간 것이 있다. a를 주우면 000001 로 표현된다는 이 부분을 그냥 넘어갔다.

   a를 주우면 000001로 어떻게 표현할 것인가?? 만약 저상태에서 b를 주우면 000001을 어떻게 000011 로 바꿀것인가??

   이 부분에 대해서 알아보자. 이 부분에서는 |(OR) 연산이 사용된다.

   우리가 가진 열쇠의 초기상태는 000000 일 것이다. 여기서 a를 줍는다면 1을 0칸 Shift시킨 값과 OR 연산을 해보자.

   그럼 아마 결과가 000001 로 나오게 될 것이다. 이상태에서 b를 줍는다면??

   위와 똑같이, 저 상태와, 1을 1칸 Shift시킨 값과 OR 연산을 하게되면

   000001

   000010

   ㅡㅡㅡㅡㅡ

   000011 이 나오게 될 것이다.

   * 열쇠를 주우면 | 연산을 통해서 우리가 가진 열쇠를 표시 !

   * 문을 만나면 & 연산을 통해서 우리가 문을 열수 있는지 없는지 판단 !

  

2) 본격적으로 문제를 풀어보자.

   사실 비트마스크가 문제지, 이 문제는 그리 어렵지 않다. 기본적인 BFS/DFS만 돌려주는데 그 안에 조건문을 어떻게 해야할

   지 알아보자.

   먼저 본인은 BFS를 이용해서 풀었고, Queue에서는 4개의 데이터를 관리해주었다.

   { { x, y } , { 이동횟수 , 내가현재가진 키 } } 이렇게 4개의 데이터를 관리해 주었고 Queue의 마지막 데이터인

   "내가현재가진 키" 가 비트로 표시된 000000 같은 숫자들을 의미한다.

   또한, 이미 탐색한 정점인지를 판단하기 위해서 사용된 Visit배열은 3차원 배열로 선언해주었다.

   왜냐하면, 이미 지나왔던 길이라도, 내가 특정 열쇠를 주운 후에 다시한번 지난가는 길은 다른 의미를 가지고 있기 때문이다.

   Visit[][][64] ! 갑자기 또 64가 왜나왔을까??

   키가 6개이므로 비트로 표현하면 111111이 되고, 모든 열쇠를 다 가지고 있을 경우 2^6 = 64가 되기 때문에 크기를 64로

   잡아주었다 !

   BFS안의 조건을 알아보자.

   1. 이동하려는 칸이 '.' 이거나 '1' 이면??

     → Queue에 그대로 넣어주고 계속 진행

   2. 이동하려는 칸이 열쇠라면 ? (a ~ f 라면 ?)

     → 위에서 말한대로 우리가 가지고 있는 현재 열쇠상태와 1을 해당 알파벳만큼 Shift시킨 값과 | 연산 후 열쇠상태 갱신 !

     → 이후, Queue에 넣고 계속 진행

   3. 이동하려는 칸이 문이라면 ? (A ~ F 라면 ?)

     → 위에서 말한대로 해당 알파벳만큼 1을 Shift시킨 값과 우리의 열쇠상태와 & 연산을 통해서 열 수 있는지 없는지 판단 !

    여기서 조건 2번과 3번에 대해서 코드적으로 구체적으로 알아보자.

    2번부터 보자 ! 초기에 아무런 열쇠도 없는 상태에서 열쇠 a를 주우면 어떻게 해야 할까??

    " 알파벳 a를 Index화 시켜서 그 Index번호만큼 1을 왼쪽으로 Shift시킨 후, 우리가 가진 기존의 키와 OR연산 ! "

int NewKey = 현재 가지고 있는 키 | (1 << (int(MAP[x][y] - 'a')))

  

    3번도 비슷하다 !  우리가 열쇠 a를 주운 상태에서 A를 만난다면??

    " 알파벳 A를 Index화 시켜서 그 Index번호만큼 1을 왼쪽으로 Shift시킨 후, 우리가 가진 키와 AND연산 !

int Door_Open = 현재 가지고 있는 키 & (1 << (int(MAP[x][y] - 'A')))

    이런식으로 !

 

사실 코드적으로는 저부분만 이해를 한다면 다른 부분은 크게 어려운 부분이 없다. 비트마스크 정말 기본만 알고있자 !

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<string>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M;
char MAP[MAX][MAX];
bool Visit[MAX][MAX][1 << 6];
 
pair<int, int> Start;
vector<pair<int, int>> End;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        string Inp; cin >> Inp;
        for (int j = 0; j < M; j++)
        {
            MAP[i][j] = Inp[j];
            if (MAP[i][j] == '0')
            {
                Start.first = i;
                Start.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == '1')
            {
                End.push_back(make_pair(i, j));
            }
        }
    }
}
 
bool HaveThisKey(int Cur_Key, char Door)
{
    int R_Value = Cur_Key & (1 << (int(Door) - 'A'));
 
    if (R_Value != 0) return true;
    return false;
}
 
int BFS(int a, int b)
{
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    queue<pair<int, int>> Door[26];
    Q.push(make_pair(make_pair(a, b), make_pair(0, 0)));
    Visit[a][b][0] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second.first;
        int Key = Q.front().second.second;
        Q.pop();
 
        if (MAP[x][y] == '1') return Cnt;
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx >= 0 && ny >= 0 && nx < N && ny< M)
            {
                if (Visit[nx][ny][Key] == false)
                {
                    if (MAP[nx][ny] == '.' || MAP[nx][ny] == '1')
                    {
                        Visit[nx][ny][Key] = true;
                        Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, Key)));
                    }
                    else if ('a' <= MAP[nx][ny] && MAP[nx][ny] <= 'f')
                    {
                        int Tmp_Key = Key | (1 << (int(MAP[nx][ny] - 'a')));
                        Visit[nx][ny][Tmp_Key] = true;
                        Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, Tmp_Key)));
                    }
                    else if ('A' <= MAP[nx][ny] && MAP[nx][ny] <= 'F')
                    {
                        if (HaveThisKey(Key, MAP[nx][ny]) == true)
                        {
                            Visit[nx][ny][Key] = true;
                            Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, Key)));
                        }
                    }
                }
            }
        }
    }
    return -1;
}
 
void Solution()
{
    int R = BFS(Start.first, Start.second);
    cout << R << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}