백준 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;
}