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

 

이번 문제는

 

2206번 벽 부수고 이동하기 문제와, 14923번 미로 탈출 문제와 같은 유형의 문제다.

 

다만 위 문제들은, 벽을 최대 한 번 부술 수 있다는 점인데

이번 문제는 벽을 K번 부술 수 있다는 점이 다르다.

 

14923번을 풀 때에는, VISIT을 bool로 두고 추가로 DEPTH를 두어 최단거리를 계산했는데, 그럴 필요 없이 VISIT을 int로 두어 0은 미방문, 그 외에는 최단거리 값으로 생각하여 계산하면 된다. 하나의 배열로 DEPTH와 VISIT 처리를 할 수 있다는 것이다.

 

또한 2206번을 풀 때에는 불필요하게 MAX를 사용하거나 if문을 비교적 리팩토링 하지 못하고 중복적이게 작성한 것 같은데, 이번에는 좀 더 깔끔하게 작성하여 푼 것 같다.

 

두 문제를 통해 더 잘 풀게 된 것 같다.

 

 

 

우선 N과 M의 최대값은 1000이니까 1000 x 1000 배열을 잡되

벽을 0번부터 10번까지 부술 수 있으니까, 아래와 같은 배열을 선언한다.

int VISIT[1000][1000][11];

이것이 핵심이다.

 

 

VISIT[x][y][0]의 값은

벽을 부수지 않은 상태에서 x,y 지점까지 최단거리를 저장하고 있고

 

VISIT[x][y][4]의 값은

벽을 4번 부순 상태에서 x,y 지점까지 최단거리를 저장하고 있다.

 

이처럼

VISIT의 마지막 차원인 0~10은, 벽을 k번 부순 상태에서의 이동의 의미를 갖는다.

 

안의 값이 0일 경우 아직 방문하지 않았다는 것일 테고, 1 이상일 경우 방문하여 최단거리 값을 갖고 있는 상태인 것이다.

이를 이용해 미방문을 체크하면서, 최단거리 값을 저장하는데에도 이용할 수 있다.

#include <iostream>
#include <queue>

using namespace std;


char MAP[1000][1000];
int VISIT[1000][1000][11]; // [0] ~ [10], []안의 수 : 벽을 부순 횟수. 배열 안의 값 : 해당 횟수에서의 이동.

int N, M, K;

int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};

int bfs() {
    
    queue<pair<int, pair<int, int>>> que;
    
    que.push({0, {0, 0}});
    VISIT[0][0][0] = true;
    
    
    while(!que.empty()) {
        
        
        int type = que.front().first; // 벽을 부순 횟수
        
        int x = que.front().second.first;
        int y = que.front().second.second;
        
        que.pop();
        
        
        if(x == N - 1 && y == M - 1)
            return VISIT[x][y][type];
        
        
        for(int i = 0; i < 4; i++) {
            
            int tx = x + mx[i];
            int ty = y + my[i];
            
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
            
            
            if((MAP[tx][ty] == '1' && type + 1 <= K) && VISIT[tx][ty][type + 1] == 0) { // 벽인 경우
                // K개 까지만 부수기 가능.
                
                // 벽 부수고 이동
                que.push({(type + 1), {tx, ty}});
                VISIT[tx][ty][type + 1] = VISIT[x][y][type] + 1;
                
            } else if(MAP[tx][ty] == '0' && VISIT[tx][ty][type] == 0){
                
                // 이동
                que.push({type, {tx, ty}});
                VISIT[tx][ty][type] = VISIT[x][y][type] + 1;
                
            }
        }
    }
    
    return -1;
    
}

int main() {
    
    cin >> N >> M >> K;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++)
            cin >> MAP[i][j];
    }
    
    
    
    cout << bfs() << "\n";
    
    
    
}

 

소요 시간 : 45분