[BOJ] 백준 1261 알고스팟 c++ (bfs)

문제 출처 :https://www.acmicpc.net/problem/1261 

1261번: 알고스팟

---

풀이

bfs로 생각할 수 있으나 다익스트라 개념을 도입해 풀어야하는 문제이다.

벽을 부수는 최소 수를 저장하는 dist 배열을 선언해 조건에 달아주면 된다.

 

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

int M, N;
int arr[101][101];
vector<vector<int>> dist(101, vector<int>(101, INT_MAX));
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs(){
    queue<pair<int, int>> q;
    q.push({1, 1});
    dist[1][1] = 0;
    while(!q.empty()){
        int row = q.front().first;
        int col = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++){
            int nRow = row + dy[i];
            int nCol = col + dx[i];
            if(nRow <= 0 || nRow > N || nCol <= 0 || nCol > M)
                continue;
            if(arr[nRow][nCol] == 1 && (dist[nRow][nCol] > dist[row][col] + 1)){
                dist[nRow][nCol] = dist[row][col] + 1;
                q.push({nRow, nCol});
            }
            else if(!arr[nRow][nCol] && (dist[nRow][nCol] > dist[row][col])){
                dist[nRow][nCol] = dist[row][col];
                q.push({nRow, nCol});
            }
        }
    }
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> M >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            char ch;
            cin >> ch;
            arr[i][j] = ch - '0';
        }
    }
    bfs();
    cout << dist[N][M];
    return 0;
}