[G5] 백준 11909번 배열 탈출 C++ 다익스트라

리뷰

 

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

흠.. 골드5 수준의 문제는 아닌 것 같기는 하다. 다익스트라만 써도 풀리긴 하는데 시간이 아슬아슬했다.

 

 

전역 변수

• N : 배열의 한 변의 최대값을 정의할 상수 변수
• n : 배열의 한 변의 길이를 저장할 변수
• lst : 배열의 값을 입력 받기위한 2차원 배열
• dx, dy : 2방향 탐색을 위한 방향 배열
• Pos : 현재 위치, 누적 비용, 현재 높이를 정의할 구조체, 누적 비용을 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

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

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.cx, cy = pos.cy, cv = pos.cv, ch = pos.ch;
		if (dist[cx][cy] < cv) continue;
		if (cx == n - 1 && cy == n - 1) return cv;
		//cout << "x:" << cx << " y:" << cy << " v:" << cv << " h:" << ch << "\n";

		for (int i = 0; i < 2; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nv = cv;

			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (ch <= lst[nx][ny]) {
					nv += lst[nx][ny] - ch + 1;
				}

				if (dist[nx][ny] > nv) {
					dist[nx][ny] = nv;
					pq.push({ nx, ny, nv, lst[nx][ny] });
				}
			}
		}
	}
	return -1;
}

 

출발 지점에서 도착 지점까지 이동하기 위한 최소 비용을 구하기 위한 문제

 

문제풀이

1. n값을 입력 받고, 배열 lst에 n*n크기의 값 정보를 입력 받아준다.
2. dijkstra함수를 호출해 준다.
3. Pos타입의 우선순위 큐 pq를 초기화 하고, 초기 위치 0, 0과 누적 비용 0, 현재 높이 lst[0][0]을 push해준다.
4. n*n크기의 2차원 벡터 dist를 매우 큰 값으로 초기화 해주고, 초기 위치의 값을 0으로 저장해 준다.
5. pq가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
6. 변수 cx, cy, cv, ch에 현재 위치, 누적비용, 현재 높이 정보를 파싱하여 저장해 준다.
7. 가지치기로 만약 dist[cx][cy]가 cv보다 작을 경우 continue처리해 준다.
8. 기저조건으로 도착지점에 도달한 경우 cv에 저장된 값을 리턴해 준다.
9. 2방향 탐색을 시작하고, 변수 nx, ny에 이동할 위치를 저장하고 이동할 위치가 맵의 범위 안에 있다면 이동을 진행해 준다.
10. ch가 이동할 위치보다 작거나 같다면 nv를 cv + lst[nx][ny] - ch + 1로 저장해 준다.
11. dist[nx][ny]가 nv보다 크다면 갱신 후 pq에 삽입해 준다.
12. dijkstra함수의 기저조건에 걸려 리턴한 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 도착 지점에 도달하지 못할 경우는 없다.

 

정답 코드

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

const int N = 2222;
int n;
int lst[N][N];
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };
struct Pos {
	int cx, cy, cv, ch;
	bool operator<(const Pos& other) const {
		return cv > other.cv;
	}
};

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

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.cx, cy = pos.cy, cv = pos.cv, ch = pos.ch;
		if (dist[cx][cy] < cv) continue;
		if (cx == n - 1 && cy == n - 1) return cv;
		//cout << "x:" << cx << " y:" << cy << " v:" << cv << " h:" << ch << "\n";

		for (int i = 0; i < 2; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], nv = cv;

			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (ch <= lst[nx][ny]) {
					nv += lst[nx][ny] - ch + 1;
				}

				if (dist[nx][ny] > nv) {
					dist[nx][ny] = nv;
					pq.push({ nx, ny, nv, lst[nx][ny] });
				}
			}
		}
	}
	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();
}