[백준 14442] 벽 부수고 이동하기 2

다익스트라와 dp를 사용한 문제

dp[x][y][k]로 dist배열을 선언한다.

x,y까지 벽을 k만큼 뚫으면서 갔을 때 최단거리

기본적으로 bfs를 돌리면서 dp배열을 업데이트 시켜준다.

que에는 다 넣을 필요 없이 dp배열을 업데이트 시킬 때마다 넣어준다.

출처 : 

http://wookje.dance/2017/02/22/boj-14442-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-2/

#include <stdio.h>
#include <algorithm>
#include <queue>
#define n_ 1000 + 5
#define k_ 10 + 5
using namespace std;
 
char adj[n_][n_];
int dp[n_][n_][k_];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
int n, m, k;
typedef struct Node{
    int x, y, k;
}node;
 
queue<node> q;
 
void bfs(){
    q.push({ 0, 0, 0 });
    dp[0][0][0] = 1;
    while (!q.empty()){
        node now = q.front();
        q.pop();
 
        int a = now.x;
        int b = now.y;
        int c = now.k;
 
        for (int i = 0; i < 4; i++){
            int nx = a + dx[i];
            int ny = b + dy[i];
            int nk = adj[nx][ny] - '0' + c;
            int nd = dp[a][b][c] + 1;
            if (nx == -1 || nx == n || ny == -1 || ny == m) continue;
 
            if (nk <= k&&nd < dp[nx][ny][nk]){
                dp[nx][ny][nk] = nd;
                q.push({ nx, ny, nk });
            }
        }
    }
}
 
int main(void) {
    scanf("%d %d %d", &n, &m, &k);
 
    for (int i = 0; i < n; i++){
        scanf("%s", adj[i]);
        for (int j = 0; j < m; j++){
            for (int l = 0; l <= k; l++){
                dp[i][j][l] = 0x7fffffff;
            }
        }
    }
 
    bfs();
 
    int res = 0x7fffffff;
    for (int i = 0; i <= k; i++){
        res = min(res, dp[n - 1][m - 1][i]);
    }
 
    if (res == 0x7fffffff){
        printf("-1\n");
    }
    else{
        printf("%d\n", res);
    }
 
    return 0;
}