[백준] 2206번: 벽 부수고 이동하기 (C++ 풀이)

문제

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

 

풀이

연구소 문제처럼 어떤 벽을 부술지 골라서 부시고 그때마다 bfs로 최단거리를 계산했는데 시간초과가 나왔다.

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

라는 문구가 핵심이었던 것 같다.

거리를 저장해놓는 d배열을 3차원으로 만들어서 벽을 부셨는지 유무를 체크하면서 bfs탐색을 했다.

d[x좌표][y좌표][벽]이고 벽을 부술 수 있는 기회는 한 번 뿐이므로 1은 벽을 부술 수 있음을 나타내고 0은 벽을 이미 부순 것을 의미한다.

이전 코드에선 벽 부수고 bfs하고 벽 메꾸고, 벽 부수고 bfs하고 벽 메꾸고,,, 이런식으로 해서 bfs를 n^2번했는데

d배열을 3차원으로 벽을 한 번 부셨는지 안부셨는지에 따라 bfs탐색 한 번으로 최단거리를 계산하니까

메모리는 좀 커질지 몰라도 시간은 엄청 단축했다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 1001;
int n, m;
int a[MAX][MAX];    
int d[MAX][MAX][2];    //1: 벽 부수기 가능, 0: 벽 이미 한번 부숨
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
int bfs() {
    queue<pair<pair<int, int>, int>> q;
    q.push({ {1,1},1 });
    d[1][1][1] = 1;    //시작점, 벽 부수기 가능, 거리 1로 시작
 
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int wall = q.front().second;
        q.pop();
 
        if (x == n && y == m) //(n,m)에 도착했으면 거리 return
            return d[x][y][wall];
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
 
            if (nx > 0 && nx <= n && ny > 0 && ny <= m) {
                if (a[nx][ny] == 1 && wall) {    //벽이 있고 아직 부술 기회가 있으면
                    d[nx][ny][wall - 1] = d[x][y][wall] + 1;
                    q.push({ {nx, ny}, wall - 1 });    //부수고 이동
                }
                else if (a[nx][ny] == 0 && d[nx][ny][wall] == 0) {    //벽이 없고 아직 방문 안했으면
                    d[nx][ny][wall] = d[x][y][wall] + 1;
                    q.push({ {nx, ny}, wall });    //그냥 이동
                }
            }
        }
    }
 
    return -1;
}
 
int main() {
    scanf("%d %d", &n, &m);    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%1d", &a[i][j]);
 
    printf("%d", bfs());
    return 0;
}

 

결과