백준 4485 : 녹색 옷 입은 애가 젤다지?

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

전형적인 다익스트라 알고리즘 문제이다.

한 지점을 기준으로 특정 지점까지 최단경로를 구하고 양수인 가중치가 주어질 때 다익스트라를 활용할 수 있다.

각 점을 기준으로 상,하,좌,우가 연결되있고 priority_queue에 최단경로를 갱신하면서 넣어주면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <iostream> #include <queue> #define MAX 126 #define INF 1000000000 using namespace std; int matrix[MAX][MAX]; int dist[MAX][MAX]; //left top right down int curx[] = {-1, 0, 1, 0}; int cury[] = {0, -1, 0, 1}; struct Vertex{ int i, j, dist; bool operator < (const Vertex &v) const { return dist > v.dist; } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int tc = 0; while(++tc){ int n; cin >> n; if(n==0) break; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cin >> matrix[i][j]; dist[i][j] = INF; } } dist[1][1] = matrix[1][1]; priority_queue<Vertex> pq; pq.push({1, 1, dist[1][1]}); while(!pq.empty()){ Vertex curVertex = pq.top(); pq.pop(); for(int dir = 0; dir < 4; dir++){ int ni = curVertex.i + curx[dir]; int nj = curVertex.j + cury[dir]; if(ni < 1 || ni > n || nj < 1 || nj > n) continue; if(dist[ni][nj] > dist[curVertex.i][curVertex.j] + matrix[ni][nj]){ dist[ni][nj] = dist[curVertex.i][curVertex.j] + matrix[ni][nj]; pq.push({ni, nj, dist[ni][nj]}); } } } cout << "Problem " << tc << ": " << dist[n][n] << '\n'; } return 0; }