[C++]알고스팟[백준1261]

처음엔 A....뭐야... 그냥 bfs로 슥삭하면되겠네....

라고 생각했지만 아니었다. 

더 많은 칸을 가야하지만 최소의 벽을 깨고 가는 경우가 있기 때문이었다. 

기냥 2차원 거리 배열을 선언해서 INF로 초기화해주자. 

어차피 시작점은 0,0 이니 거리배열 [0][0] = 0으로 해주자 

똑같이 Priority_Queue를 사용하는데 인자로 <int,int> int를 주었다. 

Vertext 하나의 위치정보가 x,y좌표이므로 ~
간선정보는 배열자체에 주어져있으므로 필요없고, 연결 노드야 현시점에서 4방향

탐색을 통한 지점일테고....

다만 시간줄이려고 cin.tie(NULL)해놓고 scanf를 써서 맞왜틀을 30분 겪었다...ㅎㅎ

나머지는 단순한 다익스트라로 쉽게 풀린답

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

<CODE>

// pda_pro12
#include<algorithm>
#include<queue>
#include<iostream>
 
#define lng(x) x.length()
#define sz(x) x.size()
#define N_ 101
#define INT 0x7fffffff
using namespace std;
 
int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 };
int n, m, a[N_][N_], dst[N_][N_];
priority_queue<pair<pair<int, int>, int>> pq; 
 
int main() {
    cin >> n >> m; 
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%1d", &a[i][j]),dst[i][j] = INT; 
    dst[0][0] = 0;
    pq.push({ {0,0},0 }); 
    while (!pq.empty()) {
        int v_x = pq.top().first.first; int v_y = pq.top().first.second; 
        int dis = -pq.top().second;
        pq.pop(); 
        if (dis > dst[v_x][v_y]) continue; 
        for (int i = 0; i < 4; i++) {
            int nx_x = v_x + dx[i]; int ny_y = v_y + dy[i]; 
            if (nx_x < 0 || nx_x >= m || ny_y < 0 || ny_y >= n) continue; 
            int n_dis = dis + a[nx_x][ny_y]; 
            if (n_dis < dst[nx_x][ny_y]) {
                dst[nx_x][ny_y] = n_dis; 
                pq.push({ {nx_x, ny_y}, -n_dis }); 
            }
        }
    }
    cout << dst[m - 1][n - 1]; 
    return 0;
}