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

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

문제

---

원문을 보면 알 수 있듯이, 왼쪽 위 기준에서 오른쪽 아래로 가는데 벽(1)을 한 번만 깰 수 있고 다음 부터는 깰 수 없다.

 

그러한 제약사항이 있는 상태에서 최단 거리를 구하면 된다.

아이디어

---

BFS를 이용하는데 Queue에 들어가는 정보가 (x,y)와 벽을 깬 적이 있는지에 대한 boolean이 들어가면 된다.

 

code

---

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAX = 1000;      // 그리드 최대 크기

// (-1, 0) (0, 1) (1, 0) (0, -1) 네 방향 이동
int dx[] = {-1, 0, 1, 0};  // 방향 배열: x 좌표
int dy[] = {0, 1, 0, -1};  // 방향 배열: y 좌표

int visit[MAX][MAX][2];    // 방문 및 이동 횟수 기록 배열
vector<vector<int>> grid;  // 그리드 정보
int N, M;                  // 그리드의 세로(N)와 가로(M) 크기

void init() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void BFS() {
    queue<pair<pair<int, int>, int>> q;
    q.push({{0, 0}, 0});
    visit[0][0][0] = 1;

    while (!q.empty()) {
        auto front = q.front();
        q.pop();
        int x = front.first.first;
        int y = front.first.second;
        int broken = front.second;

        if (x == M - 1 && y == N - 1) {
            cout << visit[y][x][broken] << endl;
            return;
        }

        for (int i = 0; i < 4; i++) {
            // 상하좌우 증가
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 인접 좌표가 범위 밖이거나 방문한 좌표일 경우
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (visit[ny][nx][broken]) continue;

            // 벽이 없는 경우
            if (grid[ny][nx] == 0) {
                visit[ny][nx][broken] = visit[y][x][broken] + 1;
                q.push({{nx, ny}, broken});
            }
            // 벽이 있고 아직 벽을 부수지 않은 경우
            else if (!broken) {
                visit[ny][nx][1] = visit[y][x][broken] + 1;
                q.push({{nx, ny}, 1});
            }
        }
    }

    // 목적지에 도달하지 못했을 경우
    cout << -1 << endl;
}

int main() {
    init();
    cin >> N >> M;
    grid.resize(N, vector<int>(M));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char c;
            cin >> c;            
            grid[i][j] = c - '0';
        }
    }
    BFS();
    return 0;
}

56번째 줄에

| visit[ny][nx][1] = visit[y][x][broken] + 1;

은 사실상

| visit[ny][nx][1] = visit[y][x][0] + 1; 

과 마찬가지다. 보다가 자주 헷갈릴 수도 있을 것이다.

 

부가설명하자면 안깬상태에서 벽을 깬 후, broken의 정보가 1로 바뀌면서 그 자리에 방문횟수를 그대로 업데이트 하는 것이다.

 

예를 들어 visit[2][3][0] = 5 인데 아래로 벽을 깨고 움직였다면,

visit[2][3][0] = 5 → visit[3][3][1] = 6으로 업데이트 하는 거라고 생각하면 된다.

 

이제 BFS의 특성상 위치가 1칸씩 퍼져나가는데

벽의 정보는 grid로 따로 저장하여 보존할 수 있고, visit을 통해 독립적으로 벽을 부수는 모든 경우의 수를 계산할 수 있다.

특히, Level 단위로 퍼지기 때문에 먼저 최단 거리에 도달하는 agent가 바로 return할 수 있어서 문제없이 도달할 수 있다.