[백준] 14923번 미로 탈출

14923 미로탈출

풀이)

bfs를 이용해서 푼 문제이다.

예전에 풀었던 벽 부수기 문제(2206번)랑 같은 방법으로 풀면 된다.

지팡이를 사용하지 않았던 경로와 지팡이를 사용한 경로가 중간에 같은 위치에서 만났을 때를 잘 처리해주면 된다.

둘 중 하나가 방문 체크를 하면 나머지 하나의 경로는 더이상 탐색을 하지 못하기 때문이다.

=> 방문 체크 배열을 3중 배열로 두고 처리한다.

bool visited[1001][1001][2];

// visited[y][x][0] : 아직 지팡이를 사용하지 않고 (ny,nx)에 방문

// visited[y][x][1] : 이미 지팡이를 사용하고 (ny,nx)에 방문

주의점

우리가 보통 문제 풀 때 행을 y 열을 x로 입력 받았는데, 여기서 입력으로 주어지는 변수들을 보면

행을 Hx 열을 Hy라고한다. 마찬가지로 Ex도 행 & Ey는 열을 가리킴

코드)

#include <stdio.h>
#include <queue>
using namespace std;
 
int N, M;
int Hx, Hy, Ex, Ey;
int map[1001][1001];
bool visited[1001][1001][2]; //[][][0]: 지팡이 아직 사용 안하고 이 위치에 도달했다는 뜻
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
struct info {
    int y, x, used;//위치, 지팡이 사용 여부 0이면 사용x
    info() {
        y = 0;
        x = 0;
        used = 0;
    }
    info(int y, int x, int used) {
        this->y = y;
        this->x = x;
        this->used = used;
    }
};
int bfs() {
    //Hx가 행을 가리킴. 햇갈릴까봐 Hx를 y라고 지칭하겠다.
    visited[Hx][Hy][0] = true;
    visited[Hx][Hy][1] = true;
    queue <info> qu;
    qu.push({ Hx,Hy,0 });
    int cnt = 1;//이동횟수
 
    while (!qu.empty()) {
        int size = qu.size();
        while (size--) {
            int y = qu.front().y;
            int x = qu.front().x;
            int used = qu.front().used;
            qu.pop();
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (ny <1 || ny >N || nx <1 || nx>M)continue;
                //목적지일때(Ex가 행을 가리킴)
                if (ny == Ex && nx==Ey) return cnt;
                
                if (used) {//지팡이 사용
                    if (visited[ny][nx][1] == false) {
                        visited[ny][nx][1] = true;
                        if (map[ny][nx] == 0) qu.push({ ny,nx,used });
                    }
                }
                else {//아직 지팡이 사용 x
                    if (visited[ny][nx][0] == false) {
                        visited[ny][nx][0] = true;
                        if (map[ny][nx] == 0)qu.push({ ny,nx,used });
                        else qu.push({ ny,nx,1 });
                    }
                }
                
            }
        }
        cnt++;
    }
    return -1;
}
 
int main() {
    scanf("%d %d %d %d %d %d", &N, &M,&Hx,&Hy,&Ex,&Ey);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    printf("%d", bfs());
    return 0;
}