[2206] 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

<문제>

맵의 크기가 최대 1000*1000일때, (1,1)에서 (N,M)까지의 최단거리는 매우 간단하게 구할 수 있다.

이 문제는 지나갈 수 없는 벽을 1회 부술 수 있다는 조건이 붙어있고

이로인해 기본적인 bfs와는 다른부분이 몇개 존재한다.

예를들어, 아래와 같은 경우를 보자

5 5
00000
11100
00001
01011
11010

(1,1)에서 (3,3)까지의 최단경로는 4이다. 이는 (2,1)의 벽을 뚫고가는 경우이며, 동시에 절대로 정답이 될 수 없다.

(5,5)로 도달하기 위해서는 무조건 (5,4)의 벽을 뚫어야 하기 때문이고, 위 입력을 통해 중간까지의 최단거리가 곧 정답으로 이어지지 않음을 확인할 수 있다.

이말을 반대로 말해보면 일반적인 bfs에서는 탐색중 재방문을 허용하지 않지만, 

이 문제에서는 재방문을 허용해야 한다. (3,3)까지 도달하는 방법은 총 두개로

벽을 부수고 도달한 거리 4, 부수지 않고 도달한 거리 6, 총 두개를 모두 저장해둘 필요성이 있다.

반대로, (3,3)까지 벽을 부수거나 부수지 않고 도달하는 거리는 각각 최단인 거리만 저장하면 되므로,

visit[N][M]처럼 작성하던걸 visit[N][M][2] 처럼 작성하면 된다.

재방문을 허용하는것은, 벽을 부수거나 부수지않은, 상태가 다를때에만 해당된다는 뜻이다.

 

그 외에는 일반적인 bfs처럼 구현하면 된다. queue에 넣는 조건은 조금 다르지만

어처피 큐에 {행, 열, 거리, 상태}의 4가지 모두 넣어주면 구현은 간단하다.

 

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int a[1001][1001], dist[1001][1001], n, m;
int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
bool visit[1001][1001][2];
queue <pair<pair<int, int>, pair<int, bool>>>q;
int f(void) {
    int y, x, ty, tx, i, cnt;
    bool flag = false;
    q.push({ { 0,0,},{1, false} });
    visit[0][0][false] = true;
    while (!q.empty()) {
        ty = q.front().first.first;
        tx = q.front().first.second;
        cnt = q.front().second.first;
        flag = q.front().second.second;
        if (ty == n - 1 && tx == m - 1)
            return cnt;
        q.pop();
        for (i = 0; i < 4; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m)continue;
            if (a[y][x] == 1 && flag == false) { //벽을 뚫고 지나가는 경우
                q.push({ {y,x},{cnt + 1,true} });
                dist[y][x] = dist[ty][tx] + 1;
                visit[y][x][flag] = true;
                continue;
            }
            if (a[y][x] == 0&&visit[y][x][flag]==false) {
                q.push({ { y,x},{cnt + 1,flag} });
                dist[y][x] = dist[ty][tx] + 1;
                visit[y][x][flag] = true;
                continue;
            }
        }
    }
    return -1;
}
int main(void) {
    int i, j;
    char s[1030] = { 0 };
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        getchar();
        scanf("%s", s);
        for (j = 0; s[j]; j++) {
            if (s[j] == '0')a[i][j] = 0;
            else a[i][j] = 1;
        }
    }
    printf("%d", f());
    return 0;
}

bfs의 최단거리를 보장한다는 특성은 여전하여 (n,m)에 처음으로 도착했을때의 cnt를 리턴하면 된다.