[백준 C++] 2206 벽 부수고 이동하기

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

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

풀이

최단거리문제지만, 모든경우의 비용이 동일한경우,
문제가 복잡하면 DFS를 돌릴때 시간초과가 날 수 있다.
이 문제처럼 벽을 1번만 뚫을 수 있다는 조건을 보면
BFS를 돌릴때 생기는 가짓수를 매번 줄일 수 있다는것.
여기서 DFS를 돌리면
깊이 파고들기에 가짓수를 줄이기보다 모든 경우를 탐색하는 꼴이 되므로 시간초과가 난다.

처음 DFS로 문제를 풀었더니 시간초과가나서..
BFS로 문제를 다시 풀었다.
BFS를 풀려고 하니 큐를 썼고, visited2차원ㅂ ㅐ열을 썼는데,
visited를 2차원배열을 쓰고 큐에 벽뚫은횟수를 포함해서 넣으니,
해당위치의 visited만으로는 벽을 몇번뚫은지 알 수 없어서 실제로 갈 수있음에도 visited만을보고 제외되는 문제가 생겼다.

이 그림처럼, 어떤 탐색이 벽을뚫고 지나가면서 어떤위치의 visited를 방문체크했으면
다른 탐색을 이용해서 해당 위치를 지나려고하면 이미 체크되서 못지나가는경우가 생긴다.
비단 벽을 뚫지않음에도 마찬가지.

여튼 벽을 뚫었다는 정보자체가 누실된다는것.
이 정보를 보안하려면, visited를 3차원으로 늘려서
벽을 n회뚫었을때의 방문체크를 따로 해야한다.

이를 통해 만든 BFS코드는 아래와 같다.

처음에 0,0 위치를 벽을 0번뚫은채 지나갔음을 체크.
큐를 이용해 bfs를 돌리며 벽뚫은 횟수에 따라, 벽을 한번도 안뚫었을시 다음에 crash + 1하여 visited를 체크하고, 벽을 한번이상 뚫었다면 아예 큐에 넣지 않았다.
여기서 bfs의 탐색이 결국 같은 level(거리가 같은 곳). 같은 레이어를 먼저 탐색하고 이어 탐색하므로,

목적지에 도달시 바로 res를 변경해주고 bfs를 종료했다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::vector; using std::stack; using std::queue;
using std::deque; using std::string; using std::pair;
using std::sort;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef pair<string, string> pss;

int N, M;
int res = 1;
bool **map, ***visited;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
void init();
void func();
void bfs();
void init() {
    scanf("%d%d", &N, &M);
    visited = new bool** [N];
    map = new bool* [N];
    for (int i = 0; i < N; i++) {
        visited[i] = new bool*[M];
        map[i] = new bool[M];
        char c;
        scanf("%c", &c); //줄바꿈문자 제거
        for (int j = 0; j < M; j++) {
            scanf("%c", &c);
            c == '1' ? map[i][j] = true : map[i][j] = false;
            visited[i][j] = new bool[2];
            visited[i][j][0] = false;
            visited[i][j][1] = false;
        }
    }
}

void func() {
    bfs();
    printf("%d", res);
}

void bfs() {
    visited[0][0][0] = true;
    queue<pair<pii, pii>> pass; //<위치>, <지나온갯수,벽뚫은 횟수>
    pass.push({ {0, 0}, {res, 0} });
    while (!pass.empty()) {
        int x = pass.front().first.first;
        int y = pass.front().first.second;
        int cnt = pass.front().second.first;
        int crash = pass.front().second.second;
        pass.pop();

        if (x == N - 1 && y == M - 1) { //도착한경우
            res = cnt;
            return;
        }

        for (int dir = 0; dir < 4; dir++) {
            int xx = x + dx[dir];
            int yy = y + dy[dir];
            if (xx < 0 || yy < 0 || xx == N || yy == M) continue;

            //현재 벽위치에 있는경우
            //벽뚫은 1회만 허용
            if (map[xx][yy] == 1) { 
                if (crash >= 1) continue;
                visited[xx][yy][crash + 1] = true;
                pass.push({ {xx, yy}, {cnt + 1, crash + 1 } });
            }
            else {
                if (visited[xx][yy][crash]) continue;
                visited[xx][yy][crash] = true;
                pass.push({ {xx, yy}, {cnt + 1, crash} });
            }
            
        }
    }
    res = -1;
}

int main(void) {
    init();
    func();


    return 0;
}