[G4] 백준 22116번 창영이와 퇴근 C++ 다익스트라

리뷰

 

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

(0, 0)에서 (n - 1, n - 1)좌표로 가능 경로상의 최대 경사의 최소값을 출력하는 문제

 

 

전역 변수

• n : 맵의 한 변의 크기를 저장할 변수
• ans : 정답을 저장하기 위한 변수, 초기값은 10억보다 큰 값으로 설정한다.
• lst : 격자 높이 정보를 저장할 2차원 배열
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 시뮬레이션 시 위치 정보와 최대 경사를 정의할 구조체, 경사 값을 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0 });
	vector<vector<int>> h(n, vector<int>(n, 2e9));
	h[0][0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d;
		if (cx == n - 1 && cy == n - 1) return cd;
		//cout << cx << " " << cy << " " << cd << "\n";

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				int nd = max(cd, abs(lst[nx][ny] - lst[cx][cy]));
				if (h[nx][ny] > nd) {
					h[nx][ny] = nd;
					pq.push({ nx, ny, nd });
				}
			}
		}
	}
	return -1;
}

 

다익스트라를 통해 출발 지점에서 목표 지점까지 경로상의 최대 경사의 최소값을 출력하는 함수

 

 

문제풀이

1. n값을 입력 받고, n * n크기의 맵 정보를 lst배열에 입력 받아주고, dijkstra함수를 호출해 준다.
2. Pos타입의 우선순위 큐 pq를 초기화 하고, 초기값 {0, 0, 0}을 push해준다.
3. n * n크기의 2차원 벡터 h의 초기값을 10억보다 큰 값으로 초기화 해준다.
4. 출발 지점인 (0, 0)위치의 h배열의 값을 0으로 초기화 해준다.
5. pq가 빌 때 까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 각 요소를 변수 cx, cy, cd에 파싱한다.
6. 기저 조건으로 만약 도착 위치에 도달했다면 cd에 저장된 값을 리턴해 준다.
7. 4방향 탐색을 진행하고, 맵의 범위 안에 있다면 이동을 진행해 준다.
8. 변수 nd에 cd와 현재 위치 - 이동 위치의 차이의 절대값을 비교해 더 큰 값으로 저장해 준다.
9. 이동할 위치의 h배열의 값이 nd보다 크다면 갱신한 후 이동 위치와 nd를 pq에 push해준다.
10. dijkstra가 기저조건에 도달해 종료되었을 경우 해당 함수의 리턴값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 경로상의 최대 경사를 유지해 주어야 하므로 max연산을 통해 기존 경사와 비교해 주어야 한다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n, ans = 2e9;
int lst[1000][1000];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

struct Pos {
	int x, y, d;
	bool operator<(const Pos& other) const {
		return d > other.d;
	}
};

int dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 0, 0 });
	vector<vector<int>> h(n, vector<int>(n, 2e9));
	h[0][0] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d;
		if (cx == n - 1 && cy == n - 1) return cd;
		//cout << cx << " " << cy << " " << cd << "\n";

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				int nd = max(cd, abs(lst[nx][ny] - lst[cx][cy]));
				if (h[nx][ny] > nd) {
					h[nx][ny] = nd;
					pq.push({ nx, ny, nd });
				}
			}
		}
	}
	return -1;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> lst[i][j];
		}
	}

	cout << dijkstra();
}