[BOJ]백준 4485번: 녹색 옷 입은 애가 젤다지?/Dijkstra

www.acmicpc.net/problem/4485

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

 

처음 다익스트라 알고리즘을 모를 때는 바보같이 BFS로 푸는 줄 알았지만.....

가중치 그래프에서 최단거리를 찾는 문제이기 때문에 다익스트라로 풀어야 한다 !!

 

#include <cstdio>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;
typedef struct { int x, y; }point;
struct compare {
	bool operator()(pair<int, point> a, pair<int, point> b) {
		return a.first < b.first;
	}
};
int main() {
	int n, map[130][130], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
	priority_queue<pair<int, point>, vector<pair<int, point>>, compare> pq;
	int k = 0;
	while(++k){
		scanf("%d", &n);
		if (!n)return 0;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)scanf("%d", &map[i][j]);

		int dist[130][130];
		fill(&dist[0][0], &dist[n + 1][n], INF);

		pq.push({ map[0][0],{0,0} });
		dist[0][0] = map[0][0];

		while (!pq.empty()) {
			int cost = -pq.top().first;
			point cur = pq.top().second;
			pq.pop();

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i], ny = cur.y + dy[i];
				int ncost = map[ny][nx];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n)continue;
				if (dist[cur.y][cur.x] + ncost < dist[ny][nx]) {
					dist[ny][nx] = dist[cur.y][cur.x] + ncost;
					pq.push({ -dist[ny][nx],{nx,ny} });
				}
			}
		}
		printf("Problem %d: %d\n",k,dist[n-1][n-1]);
	}
	return 0;
}

간단한 문제이기 때문에 설명은 생략한다

(~^-^)~