문제

문제 링크

어떻게 접근할 것인가

  • 벽을 부수는 문제이다.
  • 벽을 부수면서 가장 적게 부수면서 뚫을 수 있는 방법이 발견되면 해당 위치를 큐에 넣어주었다.

코드

#include <cstdio>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;

int main(){
    char miro[102][102];
    int d[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
    int cnt[102][102];
    int n, m, tw, tx, ty, nw, nx, ny;
    queue<pii> p;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m ; i++){
        for(int j = 0; j < n; j++){
            scanf("%1d", &miro[i][j]);
            cnt[i][j] = 1000;
        }
    } 
    cnt[0][0] = miro[0][0];
    p.push({0, 0});
    while(!p.empty()){
        pii top = p.front(); p.pop();
        tx = top.X, ty = top.Y;
        for(int i = 0; i < 4; i++){
            nx = tx + d[i][0], ny = ty + d[i][1];
            if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if(cnt[nx][ny] > cnt[tx][ty] + miro[nx][ny]){
                cnt[nx][ny] = cnt[tx][ty] + miro[nx][ny];
                p.push({nx, ny});
            }
        }
    }
    printf("%d", cnt[m-1][n-1]);
}

느낀점

  • 원래 우선순위 큐를 사용하기 떄문에 시간이 훨씬 감축되어야 하지만 그 전에 다 손절되어서 인지 우선순위큐를 사용하지 않는 경우가 훨씬 빠르게 나왔다.