[BFS] 14442번 벽 부수고 이동하기2

14442번 벽 부수고 이동하기2

 

https://www.acmicpc.net/problem/14442

 

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K 개 까지 부수고 이동하여도 된다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

 

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

예제 입력

6 4 1
0100
1110
1000
0000
0111
0000

6 4 2
0100
1110
1000
0000
0111
0000

4 4 3
0111
1111
1111
1110

 

예제 출력

15

9

-1

 

해결방법

벽 부수고 이동하기 에서 조건이 더 추가된 문제이다

 

일단, 최단 경로를 찾는 문제이기 때문에 BFS 탐색 또는 다익스트라 알고리즘을 떠올리면 된다

하지만 이 경우는 노드 간의 이동 시, +1 의 비용이 들고 벽을 부수는데는 특별한 비용이 들지 않는다

따라서 모든 경우의 비용이 '1'로 동일하므로 BFS 탐색 을 수행해야한다

 

이 문제에서는 벽을 부술 수 있는 개수를 k개로 입력 받는다

이는 3차원 배열로 표현할 수 있다

bool visited[MAX][MAX][WALL];

 

벽을 k개 까지 부술 수 있는 조건이 있으므로 마지막 차원은 k개의 최대값을 설정해준다

visited[1][1][0];		// 벽을 0개 부순 상태 + (1,1) 노드의 방문 여부
visited[1][1][1];		// 벽을 1개 부순 상태 + (1,1) 노드의 방문 여부
visited[1][1][2];		// 벽을 2개 부순 상태 + (1,1) 노드의 방문 여부
…
visited[1][1][k];		// 벽을 모두 부순 상태 + (1,1) 노드의 방문 여부

 

'벽을 부수고 이동하는 경우' 와 '벽을 부수지 않고 이동하는 경우' 를 나눈다

// 벽을 만난 경우
if(map[nx][ny] == 1){
    // 벽을 부술 수 있음!
    if(wall < k && !visited[nx][ny][wall+1]){
        q.push(node(nx,ny,wall+1,cnt+1));
        visited[nx][ny][wall+1] = true;
    }
}

// 벽이 아닌 경우
if(map[nx][ny] == 0 && !visited[nx][ny][wall]){
    q.push(node(nx,ny,wall,cnt+1));
    visited[nx][ny][wall] = true;
}

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 1001
#define WALL 11
#define INF 987654321
using namespace std;

struct node {
    int x,y,wall,cnt;
    
    node() {}
    node(int _x,int _y,int _wall,int _cnt) : x(_x),y(_y),wall(_wall),cnt(_cnt) {}
};

int n,m,k;

int map[MAX][MAX];
bool visited[MAX][MAX][WALL];

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs(){
    queue<node> q;
    q.push(node(0,0,0,1));
    visited[0][0][0] = true;
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        int wall = q.front().wall;
        int cnt = q.front().cnt;
        q.pop();
        
        if(x == n-1 && y == m-1){
            printf("%d\n",cnt);
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || ny<0 || nx>=n || ny>=m) continue;
            
            // 벽을 만난 경우
            if(map[nx][ny] == 1){
                // 벽을 부술 수 있음!
                if(wall < k && !visited[nx][ny][wall+1]){
                    q.push(node(nx,ny,wall+1,cnt+1));
                    visited[nx][ny][wall+1] = true;
                }
            }
            
            // 벽이 아닌 경우
            if(map[nx][ny] == 0 && !visited[nx][ny][wall]){
                q.push(node(nx,ny,wall,cnt+1));
                visited[nx][ny][wall] = true;
            }
        }
    }
    printf("%d\n",-1);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m >> k;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    memset(visited, false, sizeof(visited));
    bfs();
    
    return 0;
}