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

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

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

기초적인 다익스트라 알고리즘 문제이다. bfs와 다른 점으로 방문 여부를 따지지 않고 가려하는 곳에 이미 존재하는 비용과 현재 가려하려는 비용의 크기를 비교하여 조건에 맞을 때 큐에 다음 위치를 삽입한다.

#include <iostream>
#include <queue>
#define MAX 125
#define MAX_VALUE 987654321
using namespace std;

class Point {
public:
	int x, y, z;
	Point(int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

int n;
int cnt = 1; //몇번째 문제?
int mat[MAX][MAX]; //좌표정보
int d[MAX][MAX]; //비용

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

//다익스트라 알고리즘
void func() {
	queue<Point> q;
	q.push(Point(0, 0, mat[0][0])); //처음 위치의 좌표와 처음 위치에 루피를 넣는다.
	d[0][0] = mat[0][0]; //처음 위치에 루피를 넣는다.

	while (!q.empty()) {
		//맨 처음 좌표에 좌표위치와 비용을 얻고 맨 처음 원소를 삭제
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().z;
		q.pop();

		for (int i = 0; i < 4; i++) { //상하좌우 이동시킨다.
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n) { //범위 안에 있으면
				if (d[nx][ny] > z + mat[nx][ny]) { //현재 가려하는 곳에 이미 존재하는 비용과 내가 위치한 곳에서 다음번으로 가려하는 비용을 비교
					d[nx][ny] = z + mat[nx][ny]; //가려는 곳에 비용 갱신
					q.push(Point(nx, ny, z + mat[nx][ny])); //큐에 삽입
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	while(1) {
		cin >> n;
		if (n == 0) {
			break;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> mat[i][j];
				d[i][j] = MAX_VALUE; //처음에 모든 곳에 비용은 무한대로 설정
			}
		}
		func();
		cout << "Problem " << cnt << ": " << d[n - 1][n - 1] << '\n';
		cnt++;
	}
}