백준 2206번 - 벽 부수고 이동하기

백준 2206번 - 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

이 문제는 BFS(너비 우선 탐색) 문제이다.

해결 방법은 3차원 배열을 사용하는 것이다.

보통의 쉬운 수준의 BFS 문제들과 달리 '벽'이라는 장애물이 존재한다.

즉 벽을 부순 횟수를 기억해야 하는데 모든 위치에서 기억해야 하므로 3차원 배열을 사용해야 한다.

다행이 벽을 부술 수 있는 횟수가 1번 이므로 3차원 배열의 크기는 크지 않다.

 

현 위치에서 판단 할 것은 전 위치에서 벽을 뿌순 횟수이다.

tuple을 사용해도 되지만 struct를 사용하는 것도 좋다고 한다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;
struct a {
    int first;
    int second;
    int cnt;
};
int n, m;
int map[1001][1001];
bool check[1001][1001][2];
int dis[1001][1001][2];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
void bfs(int x, int y, int z) {
    queue<a>q;
    q.push({x, y, 0});
    check[x][y][0] = true;
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        z = q.front().cnt;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (check[nx][ny][z] == false) {
                    if (map[nx][ny] == 0) {
                        check[nx][ny][z] = true;
                        dis[nx][ny][z] = dis[x][y][z] + 1;
                        a temp = { nx,ny,z };
                        q.push(temp);
                    }
                    else {
                        if (z == 1)continue;
                        check[nx][ny][z] = true;
                        dis[nx][ny][1] = dis[x][y][z] + 1;
                        a temp = { nx,ny,z+1 };
                        q.push(temp);
                    }
                }
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    dis[0][0][0] = 1;
    bfs(0, 0, 0);
    int ans = 0;
    if (dis[n - 1][m - 1][0] == 0 && dis[n - 1][m - 1][1] == 0)printf("-1\n");
    else {
        ans = min(dis[n - 1][m - 1][0], dis[n - 1][m - 1][1]);
        if (ans == 0) ans = max(dis[n - 1][m - 1][0], dis[n - 1][m - 1][1]);
        printf("%d\n", ans);
    }
}

벽 부수기 2도 똑같은 유형이다. 코드를 조금만 바꾸면된다.