[BaekJoon] 1261 알고스팟 :: monton

문제

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

풀이

최소로 벽을 뚫고 지나가는 횟수를 구하는 것이므로 bfs 사용

이번에는 덱을 이용했는데 왜냐하면 visit 배열을 사용할 것인데 만약 덱을 사용하지 않으면

벽을 뚫은 최소 횟수의 방향인데도 불구하고 visit이 체크되어서 방문하지 않을 수도 있기 때문이다

이를 방지하려면 다익스트라로 구현을 하던가 덱을 사용하면 된다

나는 덱을 사용하였는데

이때 push를 할때 벽을 뚫지 않았으면 먼저 방문해야하는 곳으로 판단하여 push_front를 사용해 앞쪽에 넣어주고

벽을 뚫었으면 나중에 방문해야할 곳으로 판단하여 push_back을 사용하였다

코드

#include <iostream>
#include <deque>
using namespace std;
 
int N, M,ans=987654321;
int arr[101][101],visit[101][101];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
 
int main() {
    cin >> M >> N;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            char s;
            cin >> s;
            arr[i][j] = s - '0';
        }
    }
 
    deque<int> qx, qy, qa;
    qx.push_back(0), qy.push_back(0), qa.push_back(0);
    visit[0][0] = 1;
 
    while (!qx.empty()) {
        int x = qx.front();
        int y = qy.front();
        int a = qa.front();
        qx.pop_front(), qy.pop_front(), qa.pop_front();
 
        if (x == N - 1 && y == M - 1) {
            ans = ans < a ? ans : a;
        }
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            int na = a;
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (visit[nx][ny]) continue;
            
            visit[nx][ny] = 1;
            
            if (arr[nx][ny]) qx.push_back(nx), qy.push_back(ny),qa.push_back(na + 1);
            else qx.push_front(nx), qy.push_front(ny), qa.push_front(na);
        }
    }
    cout << ans;
}