Boj 2206 c ++ 벽 부수고 이동하기

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

 

N * M 행렬의 지도가 주어졌을 때 (1, 1)에서 (N, M) 까지 이동하기 위한 최단 경로의 길이를 구하는 문제이다.

가는 도중에 벽을 한번 부숴 경로가 짧아진다면 벽을 1번 부술 수 있다. (N, M) 지점까지 도달하는 것이 불가능한 경우에는 -1을 출력한다.

 

최단경로를 구하는 문제이다. bfs를 사용하는데, 벽을 1번 부술 수 있다는 조건이 까다롭다.

 

우선 최단거리를 구하는 방법 부터 다시 떠올려보자.

 

쉬운 최단거리

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

 

시작 지점에서 모든 지점까지의 최단거리를 구하는 문제였다. 레벨이 증가할 때마다 dist값을 +1해주는 방식으로 거리를 업데이트 해준다. 너비 우선 탐색에서 가장 먼저 도달하는 경우가 최단거리이기 때문에 visited로 최단거리가 보장된다. 물론 dist 배열을 -1로 초기화하여 visited의 역할을 대신할 수도 있다.

 

#include<iostream>
#include<queue>

using namespace std;

int mp[1001][1001];
int visited[1001][1001];
int dist[1001][1001];
int gx, gy;
int n, m;


void BFS(){

    queue<pair<int, int>> q;


    visited[gx][gy]=1;
    int cx, cy, nx, ny;
    int dx[4]={-1, 1, 0, 0};
    int dy[4]={0, 0, -1, 1};

    q.push({gx, gy});

    while(!q.empty()){
        cx=q.front().first;
        cy=q.front().second;
        q.pop();
        for(int i=0; i<4; i++){
            nx=dx[i]+cx;
            ny=dy[i]+cy;

            if(nx<0 || nx>=n || ny<0 || ny>=m)
                continue;

            if(!visited[nx][ny] && mp[nx][ny]!=0){
                visited[nx][ny]=1;
                q.push({nx, ny});
                dist[nx][ny]=dist[cx][cy]+1;
            }
        }
    }


}
int main(){

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

    cin>>n>>m;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>mp[i][j];
            if(mp[i][j]==2){
                gx=i;
                gy=j;
            }
        }
    }
    BFS();

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(dist[i][j]==0 && mp[i][j]==1)
                dist[i][j]=-1;
        }
    }


    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout<<dist[i][j]<<" ";
        }
        cout<<"\n";
    }

}

 

 

 

 

이 문제의 경우에는 '벽을 부술 수 있는 기회' 또한 반영해주어야 한다. 3차원 dist 배열을 선언한 후, 벽을 부수는 기회 사용 여부를 0 또는 1로 설정한다.

 

dist[ i ] [ j ] [ 벽 부수기 기회 사용 여부 ] -->  (i, j) 까지 도달하기까지의 최단 경로

 

이 또한 마찬가지로 출발지점을 제외한 모든 지점까지의 dist 값을 inf 로 초기화해준다.

-1이 부적합한 이유는 마지막에 dist [ 도착지점 ] [ 기회 사용 ]  에서 기회 사용 여부를 기준으로 더 작은 것을 출력할 때 -1이 나오기 때문이다.  방문되지 않은 지점은 min을 통해 무시해주기 위해 inf로 설정해준다.

 

전체 상황은 2가지가 있다.

1. 벽을 만난 경우

2. 벽을 만나지 않은 경우

 

- 벽은 만날 때 마다 부술 수 있는 경우에는 부숴주면 된다. 부수지 않고 다른 곳으로 가는 것을 예외처리 하는 동안 이미 다른 레벨의 노드가 이미 도착해 있을 수 있기 때문이다.

 

- 벽을 만나지 않은 경우에는 현재 기회 사용 여부를 그대로 넘겨주면 된다.

 

- 벽을 만났지만 기회를 모두 사용한 경우에는 다음으로 넘겨주지 않아도 된다. 이미 벽을 만나고 돌아가는 동안 다른 노드가 벽을 회피한 경로로 나아가고 있기 때문이다.

 

최종적으로 도착지점의 dist가 모두 inf가 아닌 경우에는 둘중 작은 것을 출력해주면 된다.

 

전체 코

#include <iostream>
#include <queue>
#define inf 99999999
using namespace std;

int N, M;
char str[1001][1001];
int mp[1001][1001];
int dist[1001][1001][2];
queue<pair<int, pair<int, int>>> q;

void BFS() {

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

    q.push({0, {1, 1}});

    while(!q.empty()) {
        int broken = q.front().first;
        int u = q.front().second.first;
        int v = q.front().second.second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nu = dx[i] + u;
            int nv = dy[i] + v;
            if(nu < 1 || nu > N || nv < 1 || nv > M)
                continue;
            if(mp[nu][nv] == 1 && !broken && dist[nu][nv][1] == inf){
                dist[nu][nv][1] = dist[u][v][0] + 1;
                q.push({1, {nu, nv}});
            } else if(mp[nu][nv] == 0 && dist[nu][nv][broken] == inf){
                dist[nu][nv][broken] = dist[u][v][broken] + 1;
                q.push({broken, {nu, nv}});
            } 
        }
    }
}

int main() {

    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            cin >> str[i][j];
            mp[i][j] = str[i][j] - '0';
        }
    }

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            for(int k = 0; k <= 1; k++) {
                dist[i][j][k] = inf;
            }
        }
    }
    dist[1][1][0] = 1;
    BFS();

    if(dist[N][M][0] == inf && dist[N][M][1] == inf){
            cout << "-1";
        return 0;
    }
    cout << min(dist[N][M][0], dist[N][M][1]);
}