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

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

BFS

---

1. 문제해결 아이디어

매번 칸을 이동할 때마다 지금까지 몇 개의 벽을 부쉈는지 정보를 가지고 있어야한다.

struct P를 만들고 해당 객체를 queue에서 가지고 다니게 하였다.

 

가장 중요한 visited배열이다.

visited[r][c][k] = 1  :  r, c를 방문할 때 총 k번 벽을 부수고 방문했음을 의미한다.

 

만약 다음 좌표가 3, 5이고 지금까지 부순 벽이 2개라면 visited[3][5][3]이 0인지 확인을 하고 이동해야한다.

만약 1이라면 이미 방문했다는 뜻이고,

 

BFS의 특성상 이미 방문한 곳에 뒤늦게 방문했다는 말은 

현재 경로가 절대로 더 빠른 경로가 될 수 없다는 말이다.

 

따라서 벽을 부술 수 있는 이 문제에서는 일반적인 BFS의 다음 좌표 탐색 조건인

다음 좌표에 갈 수 있고(ex. 벽이 아니고), 방문하지 않았다면 이라는 2가지 조건 외에 추가로 필요한 조건이 있다.

 

'다음 좌표가 벽이고, 최대로 부술 수 있는 벽의 개수인 10개를 넘지 않았고, 다음 좌표에 벽을 하나 더 부순 경우 방문하지 않았다면' 이라는 조건이 필요하다

---

2. 코드

#include <bits/stdc++.h>
 
using namespace std;
 
struct P{
    int r, c;       // 현재 위치
    int cnt = 1;    // 지금까지 지나온 칸 수
    int wall = 0;   // 지금까지 부순 벽의 수 
};
 
int N, M, K;
int Map[1001][1001];
int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
int visited[1001][1001][11] = {0, };
 
void input(){
    cin >> N >> M >> K;
    string in;
    for(int i = 0; i < N; i++){
        cin >> in;
        for(int j = 0; j < M; j++){
            Map[i][j] = in[j] - '0';
        }
    }
}
 
int BFS(){
    int result = 0;
    queue<P> que;
    P temp;
    temp.r = 0;  temp.c = 0;
    que.push(temp);
 
    visited[0][0][0] = 1;
 
    while(!que.empty()){
        P now = que.front();
        que.pop();
        
        // BFS 이므로 가장 먼저 도착한 경우임
        if(now.r == N-1 && now.c == M-1) return now.cnt;
        
        for(int i = 0; i < 4; i++){
            int nr = now.r + dr[i];
            int nc = now.c + dc[i];
            
            // 좌표를 넘어가는 경우
            if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
            // 이미 방문한 경우
            if(visited[nr][nc][now.wall]) continue;
            
            // 다음이 벽이 아니고, 방문하지 않았다면
            if(!Map[nr][nc] && !visited[nr][nc][now.wall]){
                visited[nr][nc][now.wall] = 1;
                que.push({nr, nc, now.cnt+1, now.wall});
            }
            // 다음이 벽이고, 벽을 최소 하나 더 부술 수 있고, 하나 더 부순 경우에 방문하지 않았다면
            if(Map[nr][nc] && now.wall < K && !visited[nr][nc][now.wall+1]){
                visited[nr][nc][now.wall+1] = 1;
                que.push({nr, nc, now.cnt+1, now.wall+1});
            }
        }
    }
    
    return -1;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    cout << BFS();
    return 0;
}