백준 4485 c++ -[PlusUltraCode]

[필자 사고]

이 문제는 전형적인 다익스트라 알고리즘의 응용버전이다

 

필자는 대부분 1차원에서 다익스트라 알고리즘을 사용했다면 이 문제를 통해 

2차원까지 확장하는 개념을 얻을 수 있게 되었다.

 

간단하게 다익스트라 알고리즘을 설명하자면 우선순위 큐에 가장 적은 비용의 index부터 탐색하는 방식이다.

 

2차원개념과 다익스트라 알고리즘을 알고 있다면 쉽게 해결할 수 있는 문제이다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;

int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };

typedef struct Node {
	int cost;
	int sero;
	int garo;
}Node;

typedef struct cmp {
	bool operator()(Node a, Node b) {
		return a.cost > b.cost;
	}
};

vector<vector<int>>  Arr;
vector<vector<int>> pathLoad;
int N;
void Input() {
	vector<vector<int>>  Arr2;
	vector<vector<int>> pathLoad2;
	
	Arr2.resize(N);
	pathLoad2.resize(N);
	for (int i = 0; i < N; i++) {
		Arr2[i].resize(N);
		pathLoad2[i].resize(N, INT_MAX);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> Arr2[i][k];
		}
	}
	Arr = Arr2;
	pathLoad = pathLoad2;
}

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}

void Dijkstra() {
	priority_queue<Node, vector<Node>, cmp> pq;
	pq.push({ Arr[0][0],0,0 });
	pathLoad[0][0] = Arr[0][0];
	while (!pq.empty()) {
		int nowSero = pq.top().sero;
		int nowGaro = pq.top().garo;
		pq.pop();
		if (nowSero == N - 1 && nowGaro == N - 1)return;
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				pathLoad[nextSero][nextGaro] > pathLoad[nowSero][nowGaro] +
				Arr[nextSero][nextGaro]) {
				pathLoad[nextSero][nextGaro] = pathLoad[nowSero][nowGaro]
					+Arr[nextSero][nextGaro];
				pq.push({ pathLoad[nextSero][nextGaro],nextSero,nextGaro });

			}
		}

	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int count = 0;

	while (1) {
		cin >> N;
		if (N == 0)break;
		count++;
		Input();
		Dijkstra();
		cout << "Problem " << count << ": " << pathLoad[N - 1][N - 1] << '\n';
	}
}