[BOJ 13219 // C++] Trains

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

 

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

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

13219번: Trains

주어진 지도 위에서, 두 역 사이를 상하좌우 움직임으로 잇는 경로 중 경로에 적힌 수의 총합이 가장 작은 경로의 그 총합 값을 찾는 문제이다. (단, -1이 적힌 칸은 지날 수 없다.)

 

이러한 총합 값의 최솟값은 다익스트라(dijkstra) 알고리즘을 이용해 계산해낼 수 있다. 이를 통해 문제를 해결하자.

 

주어지는 두 역의 위치에 -1이 있을 수도 있으므로 이에 주의하자.

또한 주어지는 좌표가 (행,열) 순이 아닌 (열,행) 순으로 주어짐에 유의하자.

 

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int N;
int sR, sC, eR, eC;
ll board[400][400];
ll dist[400][400];

int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void dijkstra() {
	dist[sR][sC] = board[sR][sC] + 1;
	priority_queue<pair<ll, pair<int,int>>> pq;
	pq.push(make_pair(-board[sR][sC] - 1, make_pair(sR, sC)));
	while (!pq.empty()) {
		ll d = -pq.top().first; int r = pq.top().second.first, c = pq.top().second.second; pq.pop();
		if (d > dist[r][c]) continue;
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr < 0 || rr >= N || cc < 0 || cc >= N || board[rr][cc] < 0) continue;
			if (dist[rr][cc] == 0 || d + board[rr][cc] < dist[rr][cc]) {
				dist[rr][cc] = d + board[rr][cc];
				pq.push(make_pair(-dist[rr][cc], make_pair(rr, cc)));
			}
		}
	}
}

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

	cin >> N >> sC >> sR >> eC >> eR;
	sR--, sC--, eR--, eC--;

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
		}
	}

	if (board[sR][sC] < 0) cout << -1;
	else {
		dijkstra();
		cout << dist[eR][eC] - 1;
	}
}