[ 백준 16933 ] 벽 부수고 이동하기3 (C++)

백준의 벽부수고 이동하기3(16933) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 낮에만 부술 수 있는 벽을 K개 까지만 부수고 최단 경로로 목적지까지 가는데 걸리는 시간을 출력하는 문제이다.

   본인은 BFS를 이용한 넓이우선탐색으로 구현해보았다.

   Queue에서는 5개의 값을 관리해 주었다.

   <int, int, int, int, string>. 각각의 역할은 다음과 같다.

   <x좌표, y좌표, 움직인칸수, 현재까지 벽을부순갯수, 아침인지 저녁인지("Morning" / "Night")>

  

   BFS의 조건문을 알아보자.

   먼저 이동하려는 다음칸이 '0' 인 경우.

   이동하려는 칸의 (x, y)좌표, 움직인칸수 + 1, 벽을 부순갯수는 그대로, 아침인지 저녁은 서로 반대 상황으로 바꿔주면된다.

   한 칸을 움직이게 되면 밤낮이 바뀌기 때문에 Morning이었다면 Night로, Night였다면 Morning으로 바꿔주고 Queue에 넣어주고

   탐색을 진행하면 된다.

   이동하려는 칸이 '1'인 경우,

   가장 먼저 고려해야 할 것이, 현재 까지 벽을 부순 갯수이다. 주어진 K개 만큼 이미 벽을 부셨다면 더 이상 벽을 부술 수 없다는

   것을 의미하고, 이동하려는 칸으로 이동할 수 없다는 것을 의미한다.

   만약, 현재까지 벽을 부순 갯수가 K개 보다 작다면 현재 상태가 밤인지 낮인지를 판단해야한다.

   만약 지금이 "Morning" 이라면, 벽을 부수고 갈 수 있으므로,

   이동하려는 칸의 (x, y)좌표, 움직인 칸수 + 1, 벽을 부순 갯수 + 1, 아침이라면 저녁, 저녁이라면 아침으로 Queue에 넣어주고

   탐색을 진행한다. 반대로 지금이 "Night"라면 벽을 부술수가 없다.

   따라서, Queue에 현재 칸의(x, y)좌표, 움직인 칸수 + 1, 벽을 부순 갯수 그대로, 아침<-> 저녁 으로 바꿔주고 Queue에 넣어준다.

   밤이라서 벽을 부수지 못하고 기다려야 하는 경우에도 움직인 칸수가 +1이 되므로 이부분에 주의하도록 하자.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<string>
#include<tuple>
 
#define endl "\n"
#define MAX 1000
#define INF 987654321
using namespace std;
 
int N, M, K;
int MAP[MAX][MAX];
bool Visit[MAX][MAX][11];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++)
    {
        string Inp; cin >> Inp;
        for (int j = 0; j < Inp.length(); j++)
        {
            MAP[i][j] = Inp[j] - '0';
            /*for (int k = 0; k < 11; k++)
            {
                Visit[i][j][k] = INF;
            }*/
        }
    }
}
 
void BFS(int a, int b)
{
    queue<pair<tuple<int, int, int>, pair<int, string>>> Q;
    Q.push(make_pair(make_tuple(a, b, 1), make_pair(0, "Morning")));
    Visit[a][b][0] = true;
 
    while (Q.empty() == 0)
    {
        int x = get<0>(Q.front().first);
        int y = get<1>(Q.front().first);
        int Cnt = get<2>(Q.front().first);
        int K_Num = Q.front().second.first;
        string Day = Q.front().second.second;
        Q.pop();
 
        if (x == N - 1 && y == M - 1)
        {
            cout << Cnt << endl;
            return;
        }
 
        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] == 0)
                {
                    if (Visit[nx][ny][K_Num] == false)
                    {
                        Visit[nx][ny][K_Num] = true;
                        if (Day == "Morning") Q.push(make_pair(make_tuple(nx, ny, Cnt + 1), make_pair(K_Num, "Night")));
                        else Q.push(make_pair(make_tuple(nx, ny, Cnt + 1), make_pair(K_Num, "Morning")));
                    }
                }
                else if (MAP[nx][ny] == 1)
                {
                    if (K_Num < K)
                    {
                        if (Visit[nx][ny][K_Num + 1] == false)
                        {
                            if (Day == "Morning")
                            {
                                Visit[nx][ny][K_Num + 1] = true;
                                Q.push(make_pair(make_tuple(nx, ny, Cnt + 1), make_pair(K_Num + 1, "Night")));
                                
                            }
                            else
                            {
                                Q.push(make_pair(make_tuple(x, y, Cnt + 1), make_pair(K_Num, "Morning")));
                            }
                        }                        
                    }
                }
            }
        }
    }
    cout << -1 << endl;
    return;
}
 
void Solution()
{
    BFS(0, 0);
}
 
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;
}