[BOJ] 14923. 미로탈출

미로 탈출

클릭시 이동합니다.

어떻게 풀까?

BFS 문제입니다!

해당 캐릭터의 이동 시간은 1이기 때문에, BFS에서 해당 도착점에 도착했을 때가 처음으로 나오는 시간이 바로 해당 지점에 도착할 수 있는 최소 시간입니다!

그리고, 만약 캐릭터가 이동하고자 하는 방향이 이전에 한 번 이동했던 방향이라면 다시 방문할 필요가 없죠.

그 말은 가고자 하는 방향을 한번 돌아서 간다는 것이기 때문입니다! 최소 시간과는 거리가 멀어지죠.

따라서, 해당 맵에 들어갔던 최소 시간을 check[y][x]에 표시합시다!

다만, 이 문제는 탈출을 하는데 조건이 하나가 더 있습니다!

바로, 마법을 쓸 수 있다는 것이지요.

이 마법의 유무가 최소를 만들 수 있는 또 다른 변수가 될 수 있습니다.

왜냐하면, 조금 늦게 왔더라도, 마법이 있고 없고에 따라서 아예 도착지점에 도착하지 못하는 경우도 있을 것이기 때문입니다!

위와 같은 경우는 마법을 이미 써버려서 갈 수 가 없죠.

우선 9초에 도착하는 공간을 잘 기억합시다.

하지만, 위와 같은 경우는 조금 늦게 도착하기는 하지만, 마법을 가지고 있기 때문에 도착지점에 도달할 수 있습니다!

만약 마법의 유무와 상관없이 시간만을 저장한다면, 결국 17이라는 시간에 도착하는 값을 저장하지 못하게 되고, 

결과적으로 잘못된 값을 반환할 것입니다! 

(위의 경우에는 -1을 반환하겠죠! 도착할 수 있음에도 불구하고!)

이를 방지하기 위해서 마법의 유무를 저장할 수 있도록 check 배열을 3차원으로 만듭시다.

check[행][열][마법의 유무]가 될 것입니다!

이제 마음편하게 bfs를 사용하시면 됩니다.

코드

#pragma once
#include<cstdio>
 
bool map[1002][1002];
int check[1002][1002][2];
int que[3000000][4], n, m;
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
 
enum TYPE{X = 0, Y = 1, T = 2, M = 3};
 
int main() {
    scanf("%d %d\n", &n, &m);
 
    int hx, hy, ex, ey;
    scanf("%d %d\n %d %d", &hy, &hx, &ey, &ex);
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d \n", &map[i][j]);
            check[i][j][1] = check[i][j][0] = 98764321;
        }
    }
    int f = 0, r = 0;
    que[r][X] = hx;
    que[r][Y] = hy;
    que[r][M] = 1;
    que[r++][T] = 0;
    int D = -1;
    check[hy][hx][1] = 0;
 
 
    while (f != r) {
        int now[4] = { que[f][0], que[f][1], que[f][2], que[f++][3] };
 
        if (now[X] == ex && now[Y] == ey) {
            D = now[T];
            break;
        }
 
        for (int d = 0; d < 4; d++) {
            int nx = now[X] + dc[d];
            int ny = now[Y] + dr[d];
            
            if (map[ny][nx]) {
                if (now[M] && check[ny][nx][0] > now[T] ) {
                    check[ny][nx][0] = now[T] ;
                    que[r][X] = nx;
                    que[r][Y] = ny;
                    que[r][M] = 0;
                    que[r++][T] = now[T] + 1;
                }
            }
            else {
                if (check[ny][nx][now[M]] > now[T]) {
                    check[ny][nx][0] = check[ny][nx][now[M]] = now[T];
                        
                    que[r][X] = nx;
                    que[r][Y] = ny;
                    que[r][M] = now[M];
                    que[r++][T] = now[T] + 1;
                }
 
            }
        }
    }
 
    printf("%d\n", D);
    return 0;
}

여담

시간 복잡도는 check의 크기와 같기 때문에 O(NM)이 될 것입니다!