[백준] 알고리즘 C++ 2206번 - 벽 부수고 이동하기문제

문제

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

2206번: 벽 부수고 이동하기

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <math.h>
#include <stack>
#include <limits.h>
#include <queue>
#include <memory.h>
using namespace std;
int n, m;
int arr[1001][1001];
int check[1001][1001][2];
queue<pair<pair<int, int>, int>> qu;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int bfs() {
    while (!qu.empty()) {
        int ox = qu.front().first.first;
        int oy = qu.front().first.second;
        int ob = qu.front().second;
        if (ox == n - 1 && oy == m - 1) {
            return check[ox][oy][ob];
        }
        qu.pop();
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + ox;
            int ny = dy[i] + oy;
            int nb = ob;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (arr[nx][ny] == 0 && !check[nx][ny][nb]) {
                check[nx][ny][nb] = check[ox][oy][ob] + 1;
                qu.push({ {nx,ny},nb });
            }
            if (arr[nx][ny] == 1 && nb == 0) {
                nb = 1;
                check[nx][ny][nb] = check[ox][oy][ob] + 1;
                qu.push({ {nx,ny},nb });
            }
        }
    }
    return -1;
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j <= m; j++) {
            if (s[j] == ' ') continue;
            arr[i][j] = s[j] - '0';
        }
    }
    qu.push({ {0,0},0 });
    check[0][0][0] = 1;
    cout << bfs();
}

해설

문제를 보면 BFS를 이용하여 최적의 방문경로를 찾아야 한다는게 눈에보인다.

하지만, 벽을 부수는 경우도 추가된 점을 유의해야 한다.

이런 유형의 문제는 현재 상태를 저장하는 BFS유형으로 좋은 문제이다.

 

문제를 도출하기 위해서 이동할 수 있는 경우를 한번 살펴보자.

1. 벽이 없는 상태인 0인 경우의 길만 간다. 즉 벽을 뚫지 않고 이동하는 경우

2. 벽을 만나 벽을 뚫고 이동하는 경우 하지만 벽은 한번만 뚫을 수 있기에 벽을 이미 한번 뚫었는지 확인하여 이동하는 경우

이 두가지의 경우를 생각하여 BFS의 함수안에 if문을 작성해줍니다.

기존의 bfs의 check배열은 x,y축을 기준으로 체크하는 2차원 배열을 사용하였지만, 이 문제에서는 현재 상태를 저장할 수 있는 배열을 하나 더 추가해줘야 하기때문에 3차원 배열로 사용합니다.

 

기저사례를 통해 n,m에 도착하면 최적의 해를 리턴하고, 기저사례에 도착하지 않는 경우는 벽에 둘러 쌓여서 이동하지 못한 경우들이 있으니 -1을 리턴해줍니다.

 

벽 부수기 문제중 여러가지들이 있는데, 이 문제들을 마스터한다면 여러 가지의 문제들을 해결 할 수 있습니다.