백준 1261 알고스팟

벽을 부수고 이동하면 가중치가 1이고, 부수지 않고 이동하면 가중치를 0이라 생각할 수 있다.

벽을 최소로 부수는 것을 구해야 하므로, 벽을 부수지 않는 경우의 수를 앞선 queue에 넣고, 부수는 경우의 수를 next_queue에 넣으면 된다.

그렇게 생각하면 앞서 풀어본 문제처럼 두 개의 queue로 나누어 풀 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
int maze[100][100];
int visit[100][100];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
int main(int argc, char** argv) {
    int n, m;
    cin >> m >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &maze[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            visit[i][j] = -1;
        }
    }
 
    queue<pair<int,int>> q;
    queue<pair<int, int>> nq;
 
    q.push(make_pair(0, 0));
    visit[0][0] = 0;
 
    while (!q.empty()) {
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
 
            if (!(nr == 0 && nc == 0)) {
                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    //벽이면 다음 queue에 넣는다. 깬 벽의 개수를 1늘려준다.
                    if (visit[nr][nc] == -1 && maze[nr][nc] == 1) {
                        nq.push(make_pair(nr, nc));
                        visit[nr][nc] = visit[row][col] + 1;
                    }
                    //빈방이면 지금 queue에 넣는다. 깬 벽의 개수는 그대로 이다.
                    if (visit[nr][nc] == -1 && maze[nr][nc] == 0) {
                        q.push(make_pair(nr, nc));
                        visit[nr][nc] = visit[row][col];
                    }
                }
            }
        }
 
        
        if (q.empty()) {
            q = nq;
            nq = queue<pair<int, int>>();
        }
    }
 
    printf("%d\n", visit[n - 1][m - 1]);
 
    return 0;
}