백준 1261번 알고스팟

백준 1261번 알고스팟

#include <iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int arr[101][101];
int m, n;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
bool visited[101][101];
void Stoi(vector<string> wall) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            arr[i][j] = wall[i][j] - '0';
}
int route(int desty,int destx) {
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    pq.push({ 0, { 0,0 } });
    visited[0][0] = 1;
    while (!pq.empty()) {
        int starty = pq.top().second.first;
        int startx = pq.top().second.second;
        int block = pq.top().first;
        pq.pop();
        if (starty == desty && startx == destx) return block;
            for (int i = 0; i < 4; i++) {
            int nexty = starty + dy[i];
            int nextx = startx + dx[i];
        
            if (nexty >= 0 && nexty < n&&nextx >= 0 && nextx < m){
                if (!visited[nexty][nextx]) {
                    if (arr[nexty][nextx] == 1) {
                        pq.push({ block + 1,{nexty,nextx} });
                    }
                    else
                        pq.push({ block,{nexty,nextx} });
                    visited[nexty][nextx] = true;
                }
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> m >> n;
    vector<string> wall(n);
    for (int i = 0; i < n; i++) {
        cin >> wall[i];
    }
    Stoi(wall);
    cout << route(n - 1, m - 1) << endl;
 
    return 0;
 
}
 

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

문제 해설은 딱히 필요없을 정도로 기본적인 응용이었습니다만.... 우선순위큐를 사용하는 법을 떠올리지 못해서

한참동안 해멨네요.... 문제도 제대로안읽어서 계속 이상하게 구현했습니다... 반성반성