취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 20046번 문제인 Road Reconstruction이다.
문제는 아래 링크를 확인하자.

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

각각의 칸을 노드로, 인접한 두 칸 A와 B에 대하여 A에서 B로 이동할 수 있는 관계를 에지로(가중치는 B의 복구비용) 갖는 그래프를 생각해보자. 이 때, 좌상단 칸에서 우하단 칸까지의 최단경로는 (좌상단 칸이 방문 가능하다는 가정 하에) 위에서 모델링한 그래프에서의 최단경로와 대응시켜 생각해볼 수 있다.

가능한 에지 가중치의 종류가 적고 가중치의 크기가 작으므로 큐를 이용한 dijkstra 또는 dial's algorithm 등도 사용할 수 있겠지만, 그냥 dijktra 알고리즘을 이용해도 무리없이 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int R, C;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
int board[1000][1000];
int dist[1000][1000];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
void dijkstra() {
	memset(dist, 0x3f, sizeof(dist));
	dist[0][0] = board[0][0];
	pq.push(make_pair(board[0][0], 0));
	while (!pq.empty()) {
		int r = pq.top().second / C, c = pq.top().second % C, d = pq.top().first; pq.pop();
		if (dist[r][c] < d) continue;
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C || board[rr][cc] == -1) continue;
			int dd = d + board[rr][cc];
			if (dd < dist[rr][cc]) dist[rr][cc] = dd, pq.push(make_pair(dd, rr * C + cc));
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}
	if (board[0][0] == -1 || board[R - 1][C - 1] == -1) {
		cout << -1;
		return 0;
	}

	dijkstra();

	if (dist[R - 1][C - 1] < 0x3f3f3f3f) cout << dist[R - 1][C - 1];
	else cout << -1;
}