[BOJ 1261] 알고스팟

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

벽을 부시면서 원하는 위치에 도달할때까지 최소한으로 벽을 부시는 경우를 구하는 문제이다.

2차원 배열 두개를 통하여 움직이고 1개를 깼을 때, 2개 .... 하다가 원하는 위치에 도달할때까지 반복하게 된다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
 
#define INF 1e18
typedef long long  ll;
 
using namespace std;
 
int arr[111][111],n,m,d[111][111];
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
 
bool chk(int y ,int x){
    return 0<y && y<=m && 0<x && x<=n;
}
 
void solve(int y, int x){
    queue<pair<int,int>> q;
    queue<pair<int,int>> nq;
    d[y][x] = 0;
    q.push({y,x});
    
    while(!q.empty()){
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++){
            int yyy = yy+dy[i];
            int xxx = xx+dx[i];
            if(chk(yyy,xxx)){
                if(d[yyy][xxx] == -1){ // 방문한 적이 없을떄
                    if(arr[yyy][xxx] == 0){
                        d[yyy][xxx] = d[yy][xx];
                        q.push({yyy,xxx});
                    }else{
                        d[yyy][xxx] = d[yy][xx]+1;
                        nq.push({yyy,xxx});
                    }
                }
                
            }
        }
        if(q.empty()){
            q = nq;
            nq = queue<pair<int,int>>();
        }
    }
}
 
 
 
int main(){
    scanf("%d%d " ,&n,&m);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%1d" , &arr[i][j]);
            d[i][j] = -1;
        }
    }
    solve(1,1);
    printf("%d\n" , d[m][n]);
    return 0;
}

그러하다. 부시고 또 부시고 또 부신다. 

+) 추가 설명

nq = queue<pair<int,int>>();

의 뜻은 "기존 nq는 destructor가 call되면서 삭제되고 그자리에 새로운 queue가 생성 이라는 의미"이다.