백준 1261:알고스팟

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

다익스트라 배열버전이예요.. 배열을 상하좌우로 연결된 그래프라고 보면 편해요. 배열을 다익스트라로 탐색하면되요.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define r first
#define c second
const char dr[4] = { 0,1,0,-1 };
const char dc[4] = { -1,0,1,0 };
 
typedef pair<int, int> pos;
typedef pair<int, pos> PAIR;
 
int main(void) {
    ios::sync_with_stdio(false);
    
    int N, M; cin >> N >> M; cin.ignore();//M이 row더라구요.. N이 col..
    priority_queue<PAIR, vector<PAIR>, greater<PAIR>> pq;
    vector<vector<bool>> visited(M, vector<bool>(N, false));
    vector<vector<int>> graph(M, vector<int>(N));
    vector<vector<int>> cost(M, vector<int>(N, M * N));
    for (auto& row : graph) {
        for (auto& col : row) {
            col = cin.get() - '0';
        }//하나씩 입력받으려면 이렇게 하나요?..
        cin.ignore();//엔터값 없애기
    }
 
    pq.push(PAIR(0, pos(0, 0)));
    cost[0][0] = 0;//시작점
 
    while (!pq.empty()) {//다익스트라 알고리즘
        pos cur;
        do {
            cur = pq.top().second; pq.pop();
        } while (!pq.empty() && visited[cur.r][cur.c]);
 
        if (visited[cur.r][cur.c]) break;
        visited[cur.r][cur.c] = true;
 
        for (int i = 0; i < 4; i++) {//좌표이므로 4방탐색
            pos next(cur.r + dr[i], cur.c + dc[i]);
            if (!(next.r < 0 || next.c < 0 || next.r >= M || next.c >= N)) {
                //범위안에 들면 새로운 최소값 갱신
                if (cost[next.r][next.c] > cost[cur.r][cur.c] + graph[next.r][next.c]) {
                    cost[next.r][next.c] = cost[cur.r][cur.c] + graph[next.r][next.c];
                    pq.push(PAIR(cost[next.r][next.c], next));
                }
            }
        }
    }
    cout << cost[M - 1][N - 1] << endl;
 
    return 0;
}