[ 백준 17244 ] 아 맞다 우산 (C++)

백준의 아 맞다 우산(17244) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 시작점에서 주어진 물건을 모두 줍고 도착점까지 갈 때 걸리는 최소 시간을 찾아야 하는 문제이다.

   본인은 이 문제를 너비우선탐색(BFS)을 이용해서 풀어보았는데, 방문체크를 단순히 '몇 개 주웠는지' 로는

   풀 수가 없다. 왜냐하면 다음과 같은 경우를 생각해보자.

  

   위와 같은 맵이 존재할 때, 우리가 주워야할 물건은 4개가 있다. 그런데 단순히 몇 개 주었는지만으로 체크를 한다면

   다음과 같은 경우가 발생할 것이다.

   시작점 → 빨강색X로 향할 때 체크 : 0개를 주웠을 때 빨강색 X에 방문한 적이 있는지 ? → 없으므로 1개를 주웠다고

   표시하며 방문 → 파랑색 X로 향할 때 체크 : 1개를 주웠을 때 파랑색 X에 방문한 적이 있는지 ? → 없으므로 파랑색 물건을

   줍고 2개를 주웠다고 표시하며 방문 → 빨강색X로 향할 때 체크 : 2개를 주웠을 때 빨강색 X에 방문한 적이 있는지 ?

   → 없으므로 3개를 주웠다고 표시하며 방문 → 파랑색 X로 향할 때 체크 : 4개를 주웠을 때 파랑색 X에 방문한 적이

   있는지 ? → 없으므로 파랑색 물건을 줍고 4개를 주웠다고 표시하며 방문 → E로 향함.

   이렇게 되면 실제로 물건을 4개다 줍지 않았음에도, 4개를 주웠다고 잘못 판단하고 결론에 도달하는 경우가 존재한다.

   따라서 단순히 '몇 개를 주었는지' 로는 문제를 해결할 수가 없다.

   접근할 때, '몇 개'가 아닌 '빨강색 X를 주웠는지' 혹은 '파랑색 X를 주웠는지' 이런 식의 개념으로 접근을 해야 한다.

   그래서 이 부분을 위해서 본인은 비트마스크를 사용했다.

   본인은 물건들을 X로 놓지 않고, 각 물건들이 입력됨과 동시에 번호로 표시해 주었다.

   예를 들면 위의 경우, 빨강색 X = '0' , 파랑색 X = '1', 나머지 X들 = '2', '3' 이런식으로 char형 문자로 저장해 주었다.

   그리고 위의 물건들을 비트마스크로 표시하는 것이다. 주웠을 때는 1, 아직 줍지 않았을 때는 0

   최종적으로 우리가 모든 물건을 다 주웠다면 모든 비트가 '1'로 표시되어 있을 것이다.

   위의 그림같은 경우 주워야할 물건이 4개이므로 '1111' 이 되어야 모두 주운 것이다.

   여기서 잘 생각해야 할 것이, 실제로 우리는 2진수로 비트를 표현하는 것이 아니라 ,10진수를 2진수 처럼 표현할 것이다.

  

2) 본인은 방문체크를 위한 bool 형 Visit배열을 3차원으로 선언해 주었다.

   크기는 Visit[50][50][35]로 선언해 주었다.

   앞에 50 50은 맵의 최대 크기, 즉 x좌표와 y좌표를 나타내는 부분이고, 뒤에 35를 한번 봐보자.

   물건은 최대 5개까지 있을 수 있다. 즉, 물건 5개를 모두 주웠다면 비트가 '11111' 로 표현되야 할 것이다.

   하지만, 우리는 실제로 2진수를 사용하는 것이 아닌 10진수를 2진수처럼 표현하는 것이다. 즉, '11111'을 십진수로

   나타내면 31이다. 즉, 물건이 최대 5개가 있더라도 '11111'보다 더 큰 수는 나오지 않기 때문에, 다시 말해서 '31'보다

   더 큰 수는 나오지 않기 때문에 배열의 크기를 31보다 조금 더 큰 35로 설정해 주었다.

   그럼 물건을 줍게되면 어떻게 체크를 해줘야 할까 ??

   예를 들어서 물건이 4개가 있고, 현재 비트가 0000 이라고 가정해보자. 즉, 아직 물건을 하나도 줍지 못한 상태이다.

   여기서 '0'번 물건을 주웠다고 가정해보면, 아마 비트는 0001이 될 것이다.

   0000 과 어떤 값을 무슨 연산을 해줘야 0001이 나올까 ?? 바로 0001과 or 연산을 하면 된다.

   0000 | 0001 = 0001 이기 때문이다.

   그럼 '1'번물건을 주웠다고 가정해보자. 아마 비트는 0010이 되어야 할 것이다.

   이 값은, 0000 | 0010 을 해주면 나오게 되는 값이다.

   즉 ! "1을 물건의 번호만큼 << shift 연산 후, or연산을 진행" 하면 되는 것이다.

   '0'번 물건을 주운 경우를 보자. 현재 비트 = 0000 이고, 위에서 말한대로 1을 물건의 번호만큼 << shift연산 후

   or 연산을 해보자. 1을 물건의 번호인 '0'만큼 shift연산을 하게되면, 0001이 될 것이다. 1은 2진수로 0001이기 때문에 !

   그 후, 0000과 0001을 or 연산을 하면 '0'번 물건을 주웠습니다 라고 표시할 수 있는 비트가 생성되는 것이다.

   '1'번 물건을 줍게 되면, 1을 '1'번만큼 << shift연산을 하게되면 0001 → 0010 이 되고, 이 후 or 연산을 하게 되면

   0010 이 되는 것이다.

   이런식으로 x번 물건을 주웠는지 안주웠는지를 체크를 해주면서 탐색을 진행하면 된다.

  

3) 위에서는 비트마스크를 이용한 풀이를 알아보았다. 본인은 또 한가지 방법으로 풀이를 해보았는데, 이 방법은

   모든 물건에 순서를 만들어 주는 것이다. 물건을 주울 순서를 정한 후, 해당 물건을 순서대로 주워보고 걸리는 시간 중

   최소값을 찾는 방식이다.

   따라서 이 풀이에는 '순열'을 구현하는 과정이 들어간다.

   순열을 구현하는 방법을 모른다면 아래의 글을 읽고 오자 !

   [ 순열 구현하기 (Click) ]

  

   각 물건들의 순서를 정해주고, BFS 탐색으로 시작점 → 순서가 정해진 물건들을 순서대로 줍기 → 도착점

   으로 가는 시간들 중, 최소 시간을 정답으로 채택하는 방식이다.

   주의해야 할 부분은 주워야 할 물건의 갯수가 0개일 때가 존재한다. 따라서, 0 개일 때는, 시작점에서 도착점으로

   바로 탐색을 해줘야 하는 것이다.

[ 비트마스크 풀이 소스코드 ]

#include<iostream>
#include<queue>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Bit;
char MAP[MAX][MAX];
bool Visit[MAX][MAX][35];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
pair<int, int> Start, End;
 
void Input()
{
    int Idx = 0;
    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'S')
            {
                Start.first = i;
                Start.second = j;
            }
            else if (MAP[i][j] == 'X')
            {
                MAP[i][j] = (Idx++) + '0';
            }
        }
    }
    
    Bit = (1 << Idx) - 1;
}
 
void Solution()
{
    queue <pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(Start.first, Start.second), make_pair(0, 0)));
    Visit[Start.first][Start.second][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 Bit_State = Q.front().second.second;
        Q.pop();
 
        if (MAP[x][y] == 'E' && Bit_State == Bit)
        {
            cout << Cnt << endl;
            return;
        }
 
        for(int i = 0 ; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nB = Bit_State;
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M)
            {
                if ('0' <= MAP[nx][ny] && MAP[nx][ny] < '5')
                {
                    nB = Bit_State | (1 << MAP[nx][ny] - '0');
                    if (Visit[nx][ny][nB] == false)
                    {
                        Visit[nx][ny][nB] = true;
                        Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, nB)));
                    }
                }
                else if (MAP[nx][ny] != '#')
                {
                    if (Visit[nx][ny][nB] == false)
                    {
                        Visit[nx][ny][nB] = true;
                        Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, nB)));
                    }
                }
            }
        }
    }
}
 
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;
}

[ 순열을 통한 풀이 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, M, Answer = 987654321;
char MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Select[5];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
vector<pair<int, int>> V, Order;
pair<int, int> Start, End;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> M >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'X')
            {
                V.push_back(make_pair(i, j));
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'S')
            {
                Start.first = i;
                Start.second = j;
                MAP[i][j] = '.';
            }
            else if (MAP[i][j] == 'E')
            {
                End.first = i;
                End.second = j;
                MAP[i][j] = '.';
            }
        }
    }
}
 
int BFS(int Sx, int Sy, int Ex, int Ey)
{
    memset(Visit, false, sizeof(Visit));
    queue<pair<pair<int, int>, int>> Q;
    Q.push(make_pair(make_pair(Sx, Sy), 0));
    Visit[Sx][Sy] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first.first;
        int y = Q.front().first.second;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (x == Ex && y == Ey) 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 (MAP[nx][ny] == '.' && Visit[nx][ny] == false)
                {
                    Visit[nx][ny] = true;
                    Q.push(make_pair(make_pair(nx, ny), Cnt + 1));
                }
            }
        }
    }
}
 
void Calculate()
{
    int S = Order.size();
    int Dist = BFS(Start.first, Start.second, Order[0].first, Order[0].second);
    for (int i = 0; i < S - 1; i++)
    {
        Dist = Dist + BFS(Order[i].first, Order[i].second, Order[i + 1].first, Order[i + 1].second);
    }
    Dist = Dist + BFS(Order[S - 1].first, Order[S - 1].second, End.first, End.second);
 
    Answer = Min(Answer, Dist);
}
 
void DFS(int Cnt)
{
    if (Cnt == V.size())
    {
        Calculate();
        return;
    }
 
    for (int i = 0; i < V.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Order.push_back(V[i]);
        DFS(Cnt + 1);
        Order.pop_back();
        Select[i] = false;
    }
}
 
void Solution()
{
    if (V.size() == 0)
    {
        Answer = BFS(Start.first, Start.second, End.first, End.second);
        cout << Answer << endl;
        return;
    }
    DFS(0);
    cout << Answer << 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;
}