[백준] 14923번 미로 탈출 (C++)

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

 

 

이 문제는 solved.ac 에 클래스 4문제 2206번 벽 부수고 이동하기 와 유사한 문제이다.

시작좌표와 도착 좌표가 주어지며 격자판에서 시작좌표에서 도착좌표로 이동할 수 있는지

만약 움직일 수 있으면 최소 이동거리를 출력하는 문제이다.

 

이때 격자판은 0, 1의 숫자로 주어지는데 0인경우 빈칸, 1인경우 벽으로(이동할 수 없는 구간)

이다. 이때 중요한점은 벽을 하나만 깰 수 있다는 점이다.

 

따라서 시작점에서 상하좌우를 탐색하며 도착점까지 이동할 때 최대 하나의 벽을 깨고 갈 수 있는 문제이다.

 

 

벽을 부쉈는지 안부쉈는지 여부에 대해서 알기 위해서 방문배열을 3차원 배열을 사용하였다.

만약 벽을 부쉈을 경우 벽을 더 부술수 없기에 하나의 차원을 0과 1로만 표현하였다.(0 -> 벽을 부수지 않은 상태, 1 -> 벽을 부순 상태)

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {0, 1, -1, 0, 1, -1, -1, 1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int N, M, startx, starty, endx, endy;
int graph[1001][1001];
bool visited[1001][1001][2];

void bfs(int a, int b) {
    queue<tuple<int, int, int, int>> q;
    q.push({a, b, 0, 0});
    visited[a][b][0] = true;

    while(!q.empty()) {
        int x = get<0>(q.front());
        int y = get<1>(q.front());
        int cnt = get<2>(q.front());
        int status = get<3>(q.front());
        q.pop();

        if(x == endx-1 && y == endy-1) {
            cout << cnt;
            exit(0);
        }

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx >= N || nx < 0 || ny >= M || ny < 0) continue;
            if(visited[nx][ny][status]) continue;
            if(status == 1 && graph[nx][ny] == 1) continue;

            if(status == 0 && graph[nx][ny] == 1) {
                q.push({nx, ny, cnt+1, 1});
                visited[nx][ny][1] = true;
                continue;
            }

            q.push({nx, ny, cnt+1, status});
            visited[nx][ny][status] = true;
        }
    }
}

void solve() {
    bfs(startx-1, starty-1);

    cout << -1;
}

void input() {
    cin >> N >> M >> startx >> starty >> endx >> endy;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> graph[i][j];
        }
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}