알고리즘 :: 백준 :: BFS :: 1261 :: 알고스팟

문제

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

문제접근

• 구하고자 하는 것이 시간이 아니라 벽 개수 라는 점을 염두하자.
• 그러므로 정점과 간선의 관계는 이렇게 나타낼 수 있다.
  
• 간선의 가중치가 2개임을 근거로 이 문제는 0, 1 BFS 로 풀 수 있음을 알 수 있다.
• 경로상에 벽이 있다면 벽을 부수고 deque에 push_back()한다.
  경로상에 벽이 없다면 deque에 push_front()한다.

코드

#include <iostream>
#include <cstring>
#include <deque>
using namespace std;

static constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
static int N, M, maze[100][100], dist[100][100];

int solve() {
    memset(dist, -1, sizeof(dist));	// -1: 방문 X, 0이상: 부순 벽 카운트
    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    dist[0][0] = 0;

    while(!dq.empty()) {
        int y = dq.front().first, x = dq.front().second;
        dq.pop_front();
        for (int i = 0; i < 4; ++i) {
            int ny = y + d[i][0], nx = x + d[i][1];
            if ((0 <= ny && ny < N) && (0 <= nx && nx < M) && dist[ny][nx] == -1) {
                if (maze[ny][nx] == 1) {
                    dq.push_back({ny, nx});
                    dist[ny][nx] = dist[y][x] + 1;
                } else {
                    dq.push_front({ny, nx});
                    dist[ny][nx] = dist[y][x];
                }
            }
        }
    }
    return dist[N - 1][M - 1];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> M >> N;
    for (int y = 0; y < N; ++y) {
        string line; cin >> line;
        for (int x = 0; x < M; ++x)
            maze[y][x] = (line[x] == '0') ? 0 : 1;
    }
    cout << solve() << '\n';
}

결과