[BOJ] 창영이와 퇴근 22116번

이번 문제는 올려주신 풀이를 거의 참고하여 풀었습니다. 다익스트라 관련 문제를 풀면서 적응할 필요가 있을 것 같네요. 다익스트라 개념을 이해하고, 코드로도 대충 어떤 식으로 짜야될지 구상은 됐는데 우선순위 큐를 어떤 식으로 활용해야 될지 몰랐습니다.

정리

• 처음에는 priority_queue에 3가지 데이터(x, y, 거리)를 pair로 담아주기만 하면 된다는 생각으로 거리를 마지막에 넣어주었는데 나중에 priority_queue의 사용 이유를 깨닫고, 순서를 바꾸어서 해결해주었습니다.
• 좌표와 좌표 사이 경사값의 최대를 구하면 되는 문제인데 익숙하지 않아서 그런지 계속 최단거리를 구하려고 했던 것 같습니다.(지금 생각해보면 왜 그랬는지 모르겠는데 다익스트라를 코드로 짜 본 적이 없어서 개념 자체를 적용해보려고 한 것 같기도 하네요.)
• 최대 경사의 최솟값이라는 의미가 잘 이해가 안 갔는데요. 최소한의 비용으로라는 의미에서 최단거리를 찾는 것이라고 생각은 했는데 예제를 보고 "최대 경사의 최솟값"이 어떤 것을 구하라고 하는지 이해했습니다.
• memset에 대해서 제대로 알 수 있었습니다. 단순히 초기화만 하는 것이라고 생각했고, 항상 1 이상의 값을 넣으면 이상하게 값이 출력되길래 쓰레기 값이 들어갔나 보다 생각했는데 왜 그러한 값이 들어갔는지 알 수 있었습니다.

 

소스코드

#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <cmath>
#include <string.h>
#include <algorithm>

using namespace std;

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

int arr[1001][1001];
int dist[1001][1001];
int n;
long long int INF, ans=0;
priority_queue<pair<long long int, pair<int, int>>, vector<pair<long long int, pair<int, int>>>, greater<pair<long long int, pair<int, int>>>> pq;

void dijkstra() {
	while (!pq.empty()) {
		long long int curcost = pq.top().first;
		int curx = pq.top().second.first;
		int cury = pq.top().second.second;
		pq.pop();

		if (dist[curx][cury] != INF) continue;
		dist[curx][cury] = curcost;

		ans = max(ans, curcost);
		if (curx == n - 1 && cury == n - 1) break;
		for (int i = 0; i < 4; i++) {
			int nextx = curx + dx[i];
			int nexty = cury + dy[i];

			if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= n) continue;
			if (dist[nextx][nexty] == INF ) {
				pq.push(make_pair(abs(arr[nextx][nexty] - arr[curx][cury]),make_pair(nextx, nexty)));
				
			}

		}
	
	}

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

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
	if (n == 1) {
		cout << 0 << '\n';
		return 0;
	}
	pq.push(make_pair(abs(arr[0][0] - arr[0][1]), make_pair(0, 1)));
	pq.push(make_pair(abs(arr[0][0] - arr[1][0]), make_pair(1, 0)));

	memset(dist, 127, sizeof(dist));

	INF = dist[0][0];

	dist[0][0] = 0;

	dijkstra();

	cout << ans << '\n';
}