[BOJ 백준] 2206번 벽 부수고 이동하기

문제

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

2206번: 벽 부수고 이동하기

접근

 BFS를 이용하여 문제를 풀었다. 이때 문제의 조건을 보면 진행하는 과정에서 벽을 단 한 번 부수고 진행할 수 있다는 조건 때문에 방문처리를 어떻게 해야 할지 막막한 분들이 있을 것이다. 이를 처리하기 위해 방문 처리를 위한 배열 visit를 기존의 2차원이 아닌 3차원으로 만들어 임의의 좌표 (X, Y)까지 오는 동안 벽을 부수온 최단 거리인지 아닌지에 대해 따로 저장해 줄 수 있다. 그렇게 진행하다 도착 좌표인 (N, M)에 도달했다면 최단 거리를 출력해주고 프로그램을 종료하면 된다. 

코드

#include <algorithm>
#include <iostream>
#include <queue>

#define endl "\n"

using namespace std;

struct go {
    int x, y, chk, counter;
};
int m, n, visit[1010][1010][2] = {0}, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string map[1010];

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> map[i];
    queue<go> q;
    q.push({0, 0, 0, 1});
    visit[0][0][0] = 1;
    while (!q.empty()) {
        go g = q.front();
        q.pop();
        if (g.x == n - 1 && g.y == m - 1) {
            cout << visit[g.x][g.y][g.chk];
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int newx = g.x + dx[i];
            int newy = g.y + dy[i];
            if (newx < 0 || newy < 0 || newx >= n || newy >= m)
                continue;
            if (map[newx][newy] == '1' && g.chk == 0 && visit[newx][newy][1] == 0) {
                q.push({newx, newy, 1, g.counter + 1});
                visit[newx][newy][1] = g.counter + 1;
            } else if (map[newx][newy] == '0' && visit[newx][newy][g.chk] == 0) {
                q.push({newx, newy, g.chk, g.counter + 1});
                visit[newx][newy][g.chk] = g.counter + 1;
            }
        }
    }
    if (visit[n - 1][m - 1][0] == 0 && visit[n - 1][m - 1][1] == 0)
        cout << "-1";

    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study