[G4] 백준 20046번 Road Reconstruction C++ 최단 경로, 다익스트라

리뷰

 

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

맨 왼쪽 위 단위 격자에서 맨 오른쪽 아래 단위 격자로 이동하기 위한 최소한의 도로 건설 비용을 계산하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• arr : 맵 정보를 저장할 2차원 배열
• n, m : 맵의 세로/가로 크기를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 위치와 누적 비용을 정의할 구조체, 누적 비용을 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

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

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.cx, cy = pos.cy, cv = pos.cv;

		if (dist[cx][cy] < cv) continue;
		if (cx == n - 1 && cy == m - 1) return cv;

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

			if (0 <= nx && nx < n && 0 <= ny && ny < m && arr[nx][ny] != -1) {
				int nv = cv + arr[nx][ny];
				
				if (dist[nx][ny] > nv) {
					dist[nx][ny] = nv;
					pq.push({ nx, ny, nv });
				}
			}
		}
	}
	return -1;
}

 

(0, 0)에서 (n-1, m-1)까지 이동에 필요한 최소 비용을 구하기 위한 함수

 

 

문제풀이

1. n, m값을 입력 받고, n*m크기의 맵 정보를 입력 받아 arr배열을 초기화한다.
2. 시작점이 -1일 경우 -1을, 아닐 경우 dijkstra함수를 호출하여 반환값을 출력한다.
3. dijkstra함수 내부에선 Pos타입의 우선순위 큐 pq를 초기화하고, 시작점의 좌표와 초기값을 push한다.
4. n*m크기의 2차원 벡터 dist를 매우 큰 값으로 초기화 하고, 시작점의 초기값을 업데이트한다.
5. pq가 빌때까지 while루프를 순회하며 매 루프마다 요소를 꺼내 변수 cx, cy, cv에 값을 파싱한다.
6. 첫 번째 기저 조건으로 dist[cx][cy]가 cv보다 작을 경우 탐색하지 않고 continue처리한다.
7. 두 번째 기저 조건으로 현재 좌표가 우측 하단일 경우 cv를 리턴한다.
8. 4방향 탐색을 수행하고, 이동할 위치가 맵의 범위를 벗어나지 않으며 -1이 아닐 경우 이동을 수행한다.
9. 변수 nv에 비용을 업데이트 하고, dist[nx][ny]가 nv보다 클 경우 갱신 후 pq에 삽입한다.
10. while문이 종료될때까지 두 번째 기저 조건에 해당하지 않은 경우 -1을 리턴한다.

 

트러블 슈팅

1. 시작점이 -1인 경우 도로 건설이 불가능한 경우이나 이에 대한 분기 처리를 수행하지 않아 WA를 받았다.
2. 위 경우 dijkstra함수를 수행하지 않고, 바로 -1을 출력하도록 수정하여 AC를 받았다.

 

참고 사항

없음

 

 

정답 코드

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

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

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

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.cx, cy = pos.cy, cv = pos.cv;

		if (dist[cx][cy] < cv) continue;
		if (cx == n - 1 && cy == m - 1) return cv;

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

			if (0 <= nx && nx < n && 0 <= ny && ny < m && arr[nx][ny] != -1) {
				int nv = cv + arr[nx][ny];
				
				if (dist[nx][ny] > nv) {
					dist[nx][ny] = nv;
					pq.push({ nx, ny, nv });
				}
			}
		}
	}
	return -1;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> arr[i][j];
	cout << (arr[0][0] == -1 ? -1 : dijkstra());
}