C++) 백준 4482 녹색 옷을 입은 애가 젤다지?

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

---

코드

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <map>

using namespace std;

#define X first
#define Y second

map<pair<int, int>, int> node;	// 정점 / 비용
map<pair<int, int>, int> d;	// 정점 / 고정비용 (최소비용)

const int INF = 125 * 125 * 9 + 1;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	priority_queue<tuple<int,int, int>, vector<tuple<int,int, int>>, greater<tuple<int,int,int>>> pq;
	// 우선 순위큐 삽입 원소 : (현재 비용, x, y)
	vector<int> ans;

	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };
	int n;
	while (true) {
		cin >> n;
		if (!n) break;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> node[{i, j}];
				d[{i, j}] = INF;
			}
		}
		d[{0, 0}] = node[{0, 0}];
		pq.push({ d[{0,0}],0,0 });

		while (!pq.empty()) {
			int curX = get<1>(pq.top());
			int curY = get<2>(pq.top());
			int curD = get<0>(pq.top());
			pq.pop();

			if (d[{curX, curY}] != curD) continue;

			for (int dir = 0; dir < 4; dir++) {
				int nxtX = curX + dx[dir], nxtY = curY + dy[dir];

				if (nxtX < 0 || nxtY < 0 || nxtX >= n || nxtY >= n) continue;
				if (d[{nxtX, nxtY}] <= curD + node[{nxtX, nxtY}]) continue;

				d[{nxtX, nxtY}] = curD + node[{nxtX, nxtY}];
				pq.push({ d[{nxtX, nxtY}], nxtX,nxtY });
			}

		}
		ans.push_back(d[{n - 1, n - 1}]);
	}
	for (int i = 0; i < ans.size(); i++)
		cout << "Problem " << i + 1 << ": " << ans[i] << "\n";
}

 

 

풀이

 

한 정점에서 모든 정점까지의 최단 거리를 구함

 

1. 다익스트라 알고리즘 기본 구조로 구현

• 큐에서 비용이 가장 적은 상태 꺼내기 (우선순위 큐 사용)
• 잘못된 경우인지 확인하기 (최단 비용이 이미 갱신된 경우)
• 다음 정점의 최단 거리 갱신하기
• 큐에 현재 상태 넣기

2. 정점은 중복되지 않으므로 map 사용 / 'x좌표, y좌표, 비용' 을 담기 위해 tuple 사용

 

3. 2차원 좌표 순회를 위해 dx, dy 사용