1261 - 알고스팟

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

2차원 평면에서 큐를 넣고 빼고 하는 코드를 적으면 왠지 귀찮을꺼같아서 각 칸을 노드처럼 썼다. 예를 들면, 각 칸의 노드 번호는 아래와 같다.

// 4x2 크기의 평면
0123
4567

1인 칸으로 가는 경우에는 벽을 부숴야하므로 가중치가 1인 간선이 있다고 생각하면 된다. (그 외에는 가중치가 0인 간선)

그럼 다익스트라로 0번 -> h*w-1번 으로 가는 최단 경로 문제가 된다.

같이 보기

 - 알고스팟: BOJ

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef pair<int, int> ii;

int dijkstra(vector<ii> adj[], int n, int s, int e){
    vector<int> cost(n, INF); /* s 로부터 i까지의 최소 비용 */
    priority_queue<ii /*(-weight, next)*/> q;
    q.push({0, s});
    cost[s] = 0;
    while(!q.empty()){
        int pos = q.top().second;
        int dist = -q.top().first;
        q.pop();
        
        for(int i=0; i<adj[pos].size(); ++i){
            ii& next = adj[pos][i]; /* (next, weight) */
            if(dist + next.second >= cost[next.first]) continue;
            q.push({-(dist+next.second), next.first});
            cost[next.first] = dist+next.second;
        }
    }
    return cost[e];
}

int h, w;
int DX[] = {0, 0,-1, 1};
int DY[] = {1,-1, 0, 0};
int nodeNumber(int y, int x){
    return y*w + x;
}

int main(){
    int i, j;
    scanf("%d %d ", &w, &h);
    char s[100][101];
    for(i=0; i<h; ++i) scanf("%s", s[i]);
    
    int nodes = h*w;
    vector<ii> adj[nodes];
    for(i=0; i<h; ++i){
        for(j=0; j<w; ++j){
            for(int d=0; d<4; ++d){
                int dy = i+DY[d], dx = j+DX[d];
                if(dy < 0 || dx < 0 || dy >= h || dx >= w) continue;
                adj[nodeNumber(i, j)].push_back({nodeNumber(dy, dx), s[dy][dx]=='1'});
                adj[nodeNumber(dy, dx)].push_back({nodeNumber(i, j), s[i][j]=='1'});
            }
        }
    }
    
    printf("%d", dijkstra(adj, nodes, 0, nodes-1));
    
    return 0;
}