14442번

14442번 - 벽 부수고 이동하기2

기존의 벽 부수고 이동하기 문제랑 비슷하다. 기본개념은 BFS인데 BFS를 어떤 방식으로 사용할지 정하면 된다. 

이때는 부수고 이동하는 개념을 맵에서 한차원 늘린다고 생각하는게 쉽다. 즉 이차원 평면이 아니라 삼차원 평면에서 BFS를 실행한다고 생각

하면 된다는 뜻이다. 처음에 하나의 평면에서 시작하면서 BFS를 진행하다가, 벽이 생기고 그 벽이 방문한 적이 없고 아직 벽을 부실 수 있는 

횟수가 남아있다면 다른 차원의 이차원 평면으로 올라가는 것이다.

이런 삼차원 평면 방식의 문제가 있었던 것 같은데 문제번호는 잘 기억나지 않는다. 아무튼 이런식으로 BFS에서 조건을 체크하면서 진행하면 벽을 부수고 이동할 수 있게 된다.

<정답 코드>

#include<iostream>
#include<queue>
using namespace std;
 
typedef struct pos {
    int x;
    int y;
    int k;
};
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int N, M, K;
int map[1001][1001];
int dist[1001][1001][11];
 
int main()
{
    //freopen("input.txt", "r", stdin);
 
    cin >> N >> M >> K;
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            char c;
            cin >> c;
            map[i][j] = c - '0';
        }
    }
 
    pos tmp = { 1,1,0 };
    queue<pos> q;
    dist[1][1][0] = 1;
    q.push(tmp);
 
    while (!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int k = q.front().k;
        q.pop();
 
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            // 다음칸이 이동가능한 칸인지 확인
            if (nx >= 1 && ny >= 1 && nx <= N && ny <= M)
            {
                // 다음칸이 빈칸이고 방문한적이 없을 때
                if(map[nx][ny]==0 && dist[nx][ny][k]==0)
                {
                    dist[nx][ny][k] = dist[x][y][k] + 1;
                    pos temp = { nx,ny,k };
                    q.push(temp);
                    continue;
                }
 
                //다음칸이 장애물이고, 부시고 온 칸이 K-1 이고, 방문한적이 없을때
                if (map[nx][ny] == 1 && k <= K - 1 && dist[nx][ny][k + 1] == 0)
                {
                    dist[nx][ny][k + 1] = dist[x][y][k] + 1;
                    pos temp = { nx,ny,k+1 };
                    q.push(temp);
                    continue;
                }
                
            }
        }
    }
 
    int MIN = 987654321;
    for (int i = 0; i <= K; i++)
    {
        if (dist[N][M][i] != 0 && dist[N][M][i] < MIN)
            MIN = dist[N][M][i];
    }
 
    if (MIN == 987654321)
        cout << "-1" << endl;
    else
        cout << MIN << endl;
 
    return 0;
}