백준 14923번 - 미로 탈출

 

www.acmicpc.net/problem/14923

14923번: 미로 탈출

최단경로를 찾는 문제입니다.

벽을 1회만 통과할 수 있는데 이러한 경우 방문처리 배열크기를 늘리지 않고 풀 수 있는 방법이 있습니다.

시작점에서부터 도착점까지 BFS를 수행하여 얻은 최단거리 정보 bfs와 (코드에서 bfs배열)

도착점에서부터 시작점까지 BFS를 수행하여 얻은 최단거리 정보 rbfs를 구한 후

특정 위치(i,j) 에서 bfs[i][j] + rbfs[i][j] 의 최소값을 구하면 단순 BFS를 이용하여 쉽게 답을 구해낼 수 있습니다.

 

벽을 한번만 통과할 수 있으므로, 시작점에서 출발한 A와 도착점에서 출발한 B가 만났을때 둘의 거리합의 최소를 구한다고 생각하면 쉽습니다 (벽까지의 최단거리를 포함)

 

비슷한 문제로는 백준 14948번 군대탈출하기가 있습니다.

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int N,M;
int sty, stx, edy, edx;
int m[1001][1001]{};
int bfs[1001][1001]{};
int rbfs[1001][1001]{};
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};

void solve(int sty, int stx, int edy, int edx, int vi[][1001]){
    queue<tuple<int,int,int>> q;
    q.push({0,sty,stx});
    vi[sty][stx] = 0;

    while(!q.empty()){
        int cd, cy, cx;
        tie(cd, cy, cx) = q.front();
        q.pop();

        for(int i=0; i<4; i++){
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            if(ny<0 || nx<0 || ny>=N || nx>=M || vi[ny][nx]!=-1) continue;
            // 벽을 만나면 더이상 나아갈 수 없으므로 push하지 않음
            if(m[ny][nx]==0) q.push({cd+1, ny, nx});
            // 벽까지의 최단거리는 필요함
            vi[ny][nx] = cd+1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    cin>>sty>>stx>>edy>>edx;
    sty--; stx--; edy--; edx--;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>m[i][j];
        }
    }
    
    memset(bfs,-1,sizeof(bfs));
    memset(rbfs,-1,sizeof(rbfs));
    solve(sty, stx, edy, edx, bfs);
    solve(edy, edx, sty, stx, rbfs);
    
    int ans = INF;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(bfs[i][j]!=-1 && rbfs[i][j]!=-1){
                ans = min(ans, bfs[i][j] + rbfs[i][j]);
            }
        }
    }

    if(ans == INF) cout<<-1;
    else cout<<ans;
}