(C++) - 백준(BOJ) 14923번 : 미로탈출

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

14923번: 미로 탈출

bfs문제였습니다.

 

풀이방법

 벽 부수고 이동하기와 같은 문제였습니다.

 

 1. bfs를 수행할 때 거리를 벽을 이미 부쉈을 때의 거리와 벽을 부수지 않았을 때의 거리를 구합니다. dist[x][y][w]로 각 상태에 따른 거리를 구할 수 있습니다. x행 ,y열의 벽의 상태 w에 대한 거리가 저장됩니다. w가 0일 때는 벽을 부수지 않은 상태, w가 1일 때는 벽을 부순상태가 됩니다. 벽이 아닌공간이 다음 방문이라면 다음 방문까지의 거리는 dist[nx][ny][w] = dist[x][y][w] + 1이 됩니다.

 

 2. 한번도 벽을 부순적이 없고 다음 방문이 벽이라면 벽을 부순뒤 부수지 않았을 때의 이전거리 + 1로 dist[nx][ny][1]을 갱신해줍니다.

 

 3. 매번 q.pop시 탈출지점에 도착했을 때는 최단거리임이 보장되기 때문에 바로 dist[x][y][w]를 반환합니다.

 

 4. 모든 벽을 1개씩 부순 뒤 bfs를 수행했으나 탈출하지 못한경우 dist[x][y][w]는 초기 갱신값인 -1입니다. -1을 반환해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using tpiii = tuple<int,int,int>;
int n, m, maze[1001][1001], dist[1001][1001][2];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

struct Coord {int x, y;} falled, escape;

int bfs(){
    memset(dist, -1, sizeof(dist));
    queue <tpiii> q;
    q.push({falled.x , falled.y, 0});
    dist[falled.x][falled.y][0] = 0;
    while(!q.empty()){
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int w = get<2>(q.front());
        q.pop();
        if(x == escape.x && y == escape.y) return dist[x][y][w];
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(1 > nx || nx > n || 1 > ny || ny > m) continue;
            if(dist[nx][ny][w] != -1) continue;

            if(!maze[nx][ny]){
                dist[nx][ny][w] = dist[x][y][w] + 1;
                q.push({nx,ny,w});
            }

            if(!w && maze[nx][ny]){
                dist[nx][ny][1] = dist[x][y][0] + 1;
                q.push({nx,ny,1});
            }
        }
    }
    return -1;
}
int main(){
    cin >> n >> m;
    cin >> falled.x >> falled.y;
    cin >> escape.x >> escape.y;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) 
            cin >> maze[i][j];
    cout << bfs();
}