문제

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

풀이

목적지 까지의 최단 거리를 알기 위해 bfs 탐색을 활용합니다. 그런데 벽을 k개 까지 부술 수 있습니다. 따라서 bfs 탐색 queue에 현재 위치뿐만 아니라 지금까지 몇개의 벽을 부셨는지에 대한 값도 저장해야 합니다.
그에 따라 현재 위치까지 도달하기 위해 몇개의 벽을 부셨는지를 저장하는 배열도 필요합니다.
dist[i][j][k] : i,j 에 도착하기 위해 k개의 벽을 부쉈을 때의 최소거리

bfs 탐색을 하며 맵의 값이 0인 경우와 1인 경우를 다르게 처리합니다. 현재 부순 벽의 개수를 ck라 할때

맵의 값이 0인 경우 벽을 부수지 않고 지나갈 수 있기 때문에 ck값을 올리지 않고 일반적인 bfs 탐색하듯이 처리할 수 있습니다. 단순히 다음 위치가 맵의 경계를 넘어갔는지(out of boundary), 다음 위치를 이미 탐색하여 더빠른 수가 있었는지에 대해 조건을 확인합니다.

맵의 값이 1인 경우 벽을 부숴야 합이다. 이때 조건이 하나 추가되어야 합니다. ck의 값이 k보다 작지 않은 경우에 ck+1로 dist 배열에 접근 할때 문제가 발생되기 때문에 continue로 넘어갑니다.
인덱스 문제를 해결했다면 dist[nextI][nextJ][ck+1] = dist[i][j][ck] + 1로 다음 위치의 최소 거리 값을 저장할때 ck+1의 벽을 부순 위치에 기록해야 합니다.
또한 다음 큐에 push 할때에도 queue.push({nextI, nextJ, ck+1})로 하여 벽 하나를 부순 처리를 해야 합니다.

bfs 탐색이 끝나면 dist[i][j][0] ~ dist[i][j][k]의 수들 중에서 최소값을 선택하여 출력하면 됩니다.

코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct State
{
    int x;
    int y;
    int k=0;
};

int n, m, k;
vector<vector<char>> map;
vector<vector<vector<int>>> dist;
vector<int> dx {0, 0, -1, 1};
vector<int> dy {1, -1, 0, 0};

int min(int a, int b) { return a < b ? a : b; }

bool OOB(int x, int y)
{
    return x < 0 || x >= n || y < 0 || y >= m;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> n >> m >> k;
    map.resize(n, vector<char>(m));
    dist.resize(n, vector<vector<int>>(m, vector<int>(k+1, 0))); // map[i][j]까지 가기위해 k 개 벽을 부순상태
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<m; ++j)
        {
            cin >> map[i][j];
        }
    }

    queue<State> q;
    q.push({0,0,0});
    dist[0][0][0] = 1; // 출발지점도 카운트에 포함

    while (!q.empty())
    {
        int cx = q.front().x;
        int cy = q.front().y;
        int ck = q.front().k;
        q.pop();
        
        for (int d=0; d<4; ++d)
        {
            int nx = cx + dx[d];
            int ny = cy + dy[d];

            if (OOB(nx, ny))
                continue;

            if (map[nx][ny] == '0')
            {
                if (dist[nx][ny][ck] != 0)
                    continue;

                q.push({nx, ny, ck});
                dist[nx][ny][ck] = dist[cx][cy][ck] + 1;
            }
            else 
            {
                if (ck >= k)
                    continue;
        
                if (dist[nx][ny].at(ck+1) != 0)
                    continue;

                q.push({nx, ny, ck+1});
                dist[nx][ny][ck+1] = dist[cx][cy][ck] + 1;

            }
        }
    }
        
    int answer = INT32_MAX;
    for (auto a : dist[n-1][m-1])
    {
        if (a == 0)
            continue;

        answer = min(a, answer);
    }
    if (answer == INT32_MAX)
        answer = -1;

    cout << answer << endl;
    
    return 0;
}