[BOJ] 벽 부수고 이동하기2

문제

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이라고 가정하자.

 

풀이

14442

맞았습니다!!

16928

248

C++14 / 수정

1848

32초 전

 

1. 완전 탐색 

 

2. 벽을 부수고 들린 좌표와 벽을 부수지 않고 들린 좌표를 구분해야 한다. visited를 3차원으로 생성해서 부순 벽의 수를 저장한다. 

 

3. 최대 3개이기 때문에 조합을 돌릴 필요는 없다. (반드시 3개이면 조합을 돌리는 것이 좋다.)

 

4. 큐에는 [현재 이동한 칸의수(step), 부술 수 있는 벽의수 (crash), 현재 좌표] 이렇게 저장한다. 

 

5. 이동하다가 (n-1 ,m-1)에 도착햇다면 최소값을 비교한다. 

 

6. 이동 중에 벽을 만났다면 방문 표시를 한 후에 crash가 아직 0보다 클 때 (부술 수 있는 기회가 남아있을 때)

crash의 값을 1만큼 감소시키고 다시 이동한다. 

 

7. 벽이 아닌 그냥 길을 만났을 때는 방문 표시 후 큐에 넣어준다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, m, k, map[1001][1001], ans = 987654321;
bool visited[1001][1001][11];
 
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
 
typedef pair<int, int> pp;
typedef pair<pp, pp> pppp;
 
void bfs() {
    queue<pppp> q;
 
    q.push(pppp(pp(1, k), pp(0,0))); //현재 움직인 거리의 수, 깬 벽이 k까지니까 0이 되면 더 이상 깰 수 없다. 현재좌표 
 
    visited[0][0][k] =true;
 
    while(!q.empty()) {
        int x = q.front().second.first;
        int y = q.front().second.second;
        int step =q.front().first.first;
        int crash = q.front().first.second;
 
        q.pop();
 
        if (x == n-1 && y ==m-1) {
            ans = min(ans, step);
            break;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || visited[nx][ny][crash])
                continue;
 
            if (map[nx][ny]) {
                //벽일 때 
                if (crash>0) {
                    //아직 벽을 부술 수 있는 기회가 남아있을 경우 
                    visited[nx][ny][crash] = true;
                    q.push(pppp(pp(step+1, crash-1), pp(nx, ny)));
                }
            }
            else {
                visited[nx][ny][crash] = true;
                q.push(pppp(pp(step+1, crash), pp(nx, ny)));
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> k;
 
    for (int i = 0; i < n; i++) {
        string tmp;
        cin >> tmp;
 
        for (int j = 0; j < m; j++) {
            map[i][j] = tmp[j] - 48;
        }
    }
    //input 
 
    bfs();
 
    if (ans == 987654321) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}