[BaekJoon/백준] 14923번 미로 탈출

 

한시간 붙잡다가, 풀이 방법에 대해 검색을 조금 해보고 풀었다.

 

풀이의 핵심은 두가지다.

 

1. 입력은 1 based index이고, 배열은 0 based index
2. VISIT[1000][1000]을 두 가지로 구분한다. 
   하나는 지팡이를 사용했을때의 이동에 대한 경로 VISIT[1000][1000][0]
   하나는 지팡이를 사용하지 않았을때의 이동에 대한 경로 VISIT[1000][1000][1]

 

bfs 한 번으로 해결이 가능하다.
지팡이 사용한 상태에서의 움직임과 지팡이 사용하지 않은 상태에서의 움직임으로 나누기 때문이다.
 

어차피 지팡이 두번 사용해야 할 경우에 마주한다면, 이미 사용한 상태에서는 방문하지 못하게 되고, 사용하지 않은 상태에서의 움직임에서만 갈 수 있게 되기에 최단 경로 계산에 문제가 되지 않는 것이었다.

 

 

핵심

• 벽을 부순 적이 없는데, 벽이 아닌 곳을 마주한다면, 이동한다
• 벽을 부순 적이 없는데, 벽을 마주한다면, 벽을 부수고 이동한다
• 벽을 부순 적이 있는데, 벽이 아닌 곳을 마주한다면, 이동한다

 

VISIT[X][Y][0] 은, 벽을 부순 적이 없는 상태에서 이동하는 과정에서 사용하고

VISIT[X][Y][1] 은, 벽을 부순 적이 있는 상태에서 이동하는 과정에서 사용한다.

#include <iostream>
#include <queue>
#define MIN(a, b) ((a<=b)?a:b)
#define MAX(a, b) ((a>=b)?a:b)


using namespace std;


int MAP[1000][1000];
bool VISIT[1000][1000][2]; // 0 : 지팡이 사용 안한 상태에서의 움직임. 1 : 지팡이 사용한 상태에서의 움직임.
int DEPTH[1000][1000][2];

int N, M;
int Hx, Hy, Ex, Ey;


int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};

int bfs(int x, int y) {
    
    
    queue<pair<int, pair<int, int>>> que; // (지팡이 사용 유무, x, y)
    
    que.push({0, {x, y}});
    VISIT[x][y][0] = VISIT[x][y][1] = true;
    
    
    while(!que.empty()) {
        
        
        int isUsed = que.front().first;
        
        int x = que.front().second.first;
        int y = que.front().second.second;
        
        if(x == Ex && y == Ey)
            return DEPTH[x][y][isUsed];

        
        que.pop();
        
        for(int i = 0; i < 4; i++) {
            
            int tx = x + mx[i];
            int ty = y + my[i];
            
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
                        
            if(isUsed == 0) { // 지팡이 사용 안한 상태라면
                
                if(!VISIT[tx][ty][0] && MAP[tx][ty] == 0) { // 가려는 곳이 도로
                    que.push({0, {tx, ty}});
                    VISIT[tx][ty][0] = true;
                    DEPTH[tx][ty][0] = DEPTH[x][y][0] + 1;
                }
                if(!VISIT[tx][ty][1] && MAP[tx][ty] == 1) { // 가려는 곳이 벽이면, 사용해서 뚫음
                    que.push({1, {tx, ty}});
                    VISIT[tx][ty][1] = true;
                    DEPTH[tx][ty][1] = DEPTH[x][y][0] + 1;
                }
            } else { // 지팡이 사용한 상태라면
                
                if(!VISIT[tx][ty][1] && MAP[tx][ty] == 0) { // 가려는 곳이 도로여만 가능
                    que.push({1, {tx, ty}});
                    VISIT[tx][ty][1] = true;
                    DEPTH[tx][ty][1] = DEPTH[x][y][1] + 1;
                }
                
            }
        }
    }
    return -1;
}

int main() {
    
    cin >> N >> M >> Hx >> Hy >> Ex >> Ey;
    
    Hx--; Hy--; Ex--; Ey--; // 문제에서의 시작점과 내 시작점은 차이가 있음.
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    

    cout << bfs(Hx, Hy) << "\n";
    
}

 

 

소요 시간 : 2시간