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

문제 링크: https://www.acmicpc.net/problem/14442

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

<문제 풀이> BFS 알고리즘

 

BFS를 사용하여 최단거리를 찾을 때, 현재까지 몇 개의 벽을 부쉈는지를 체크하기 위해서 3차원 visited 배열을 다음과 같이 선언합니다.

 

visited[N][M][K] : (N,M) 좌표를 K개의 벽을 부수고 방문했을 때의 최단 거리

 

BFS의 큐에는 (좌표, 현재까지 몇 개의 벽을 부쉈는지)에 대한 정보를 담고,  다음과 같은 조건을 만족할 때 큐에 삽입합니다.

 

1. 다음 좌표가 벽일 때

벽을 부술 수 있는 횟수(K)가 남아있고 && 현재 좌표에서 벽을 부수고 다음 좌표를 방문했을 때 거리가 더 짧은 경우

 

2. 다음 좌표가 벽이 아닐 때

현재 좌표에서 다음 좌표를 방문했을 때 거리가 더 짧은 경우

 

 

 

<C++소스코드>

 

#include<iostream>
#include<cstring>
#include<queue>
#include<utility>
#include<tuple>
#include<algorithm>
using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;
const int MAX_K = 10;
const int dx[4] = { 0, 0, 1, -1 };
const int dy[4] = { 1, -1, 0, 0 };
const int INF = 0x3f3f3f3f;
bool board[MAX_N + 1][MAX_M + 1];
int dist[MAX_N+1][MAX_M+1][MAX_K + 1];

int N, M, K;

bool OOB(int x, int y) {
    return (x < 1 || y < 1 || x > N || y > M);
}

int bfs() {
    memset(dist, 0x3f, sizeof(dist));
    queue<tuple<int, int, int> > Q;
    Q.push({ 1, 1, 0});
    dist[1][1][0] = 1;
    
    while (!Q.empty()) {
        auto cur = Q.front(); Q.pop();
        int cx, cy, cnt; tie(cx, cy, cnt) = cur;
        for (int dir = 0; dir < 4; dir++) {
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];
            if (OOB(nx, ny)) continue;

            if (board[nx][ny] == 1) {
                //벽 부수기 O
                if (cnt < K &&  dist[cx][cy][cnt] + 1 < dist[nx][ny][cnt + 1]) {
                    Q.push({ nx,ny, cnt + 1 });
                    dist[nx][ny][cnt + 1] = dist[cx][cy][cnt] + 1;
                }   
            }
            else {
                if (dist[cx][cy][cnt] + 1 < dist[nx][ny][cnt]) {
                    Q.push({ nx, ny, cnt });
                    dist[nx][ny][cnt] = dist[cx][cy][cnt] + 1;
                }
            }
        }
    }

    int ans = INF;
    
    for (int i = 0; i <= K; i++) {
        ans = min(ans, dist[N][M][i]);
    }
    if (ans >= INF) return -1;
    else return ans;
}

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

    cin >> N >> M >> K;
    
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            char c; cin >> c;
            board[i][j] = c - '0';
        }
    }

    cout << bfs();
    
    return 0;
}