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

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

( 문제 바로가기 )

[ 문제설명 ]

- 입력으로 맵의 가로,세로의 길이가 주어지고 맵이 하나 주어진다. 그리고 부술수 있는 벽의 최대의 갯수가 주어진다.

- 맵에서 0은 갈 수 있는 곳, 1은 벽이라서 갈 수 없는 곳이다.

- 여기서 벽을 부술 수 있는 최대 갯수 이내에서 가장 마지막 지점까지 (0,0) ~ (N-1, M-1)까지 갈 수 있는 최단거리를 구하면

  되는 문제이다.

[ 문제풀이 ]

1. 일반적인 BFS / DFS문제 풀이법에서 약간만 변형한다면 쉽게 풀 수 있는 문제이다.

2. 일반적인 BFS / DFS같은 경우, 벽이 있거나, 이미 방문한 지점에 대해서는 재탐색을 하지 않는 것이 일반적이지만, 이 문제

   의 경우 벽이라고 해도 부술 수 있기 때문에 약간의 조건을 바꿔줘야 한다.

3. 먼저 Queue에 가장 먼저 4개의 int 값을 넣어주었다. (x,y)와 (지나온칸수, 부순벽의갯수) 이렇게 4개를 넣어주었다.

   (Q.push(make_pair(make_pair(0,0), make_pair(1, 0)))

4. 그리고 방문한 점을 표시하는 Visit 배열을 3차원 배열을 사용하였다.

   Visit[a][b][c] 인데, 여기서 [a]][b]는 x, y 좌표를 의미하고 [c]는 지금까지 뿌순 벽의 갯수를 의미한다.

   즉, Visit[a][b][c] = true 라는 것은, (a,b)라는 좌표에 오기까지 벽을 c개 뿌수고 온 적이 있음을 의미한다.

5. 또한 하나더 고려해 줘야 할 것이 벽을 부술 수 있는 갯수가 제한되어 있다는 점이다. 무한개를 부술수 있는 것이 아니기

  때문에 벽을 만날 때 마다, 이미 방문했는지 체크해보는 것도 중요하지만, 벽을 부순 횟수가, 최대횟수를 넘는지도

  체크해줘야 한다. 이 부분만 유의한다면 쉽게 풀 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<queue>
 
#define endl "\n"
#define MAX 1000
using namespace std;
 
int N, M, K;
int MAP[MAX][MAX];
bool Visit[MAX][MAX][10];
 
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.size(); j++)
        {
            int I_Inp = Inp[j] - '0';
            MAP[i][j] = I_Inp;
        }
    }
}
 
void Solution()
{
    bool Can_Go = false;
    queue<pair<pair<int, int>, pair<int, int>>> Q;
    Q.push(make_pair(make_pair(0, 0), make_pair(1,0)));
    Visit[0][0][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 Wall = 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 (Visit[nx][ny][Wall] == false)
                {
                    if (MAP[nx][ny] == 0)
                    {
                        Visit[nx][ny][Wall] = true;
                        Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, Wall)));
                    }
                    else if (MAP[nx][ny] == 1)
                    {
                        if (Wall < K)
                        {
                            Visit[nx][ny][Wall + 1] = true;
                            Q.push(make_pair(make_pair(nx, ny), make_pair(Cnt + 1, Wall + 1)));
                        }
                    }
                }
            }
        }
    }
 
    cout << -1 << 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;
}