백준 20046번, Road Reconstruction

 

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

20046번: Road Reconstruction

요약

 

(1,1) 지점에서 (N,M) 지점으로 이어지는 경로를 만든다.

---

1. 미리 정해진 도시의 상태가 주어진다. 이때, 도로가 이미 존재하는 장소, 도로를 건설할 수 있는 장소, 도로를 건설할 수 없는 장소 3가지로 분류된다.

 

2. 도로가 이미 존재하는 장소는 비용이 0, 도로를 건설할 수 있는 장소는 가중치가 존재, 도로를 건설할 수 없는 장소는 간선이 존재하지 않는 그래프로 바꾸어 다익스트라로 풀이할 수 있다.

 

3. 다익스트라의 시간 복잡도는 $O\left ( \left| E\right|log\left|E \right| \right )$이고, 정점의 개수가 최대 1000 * 1000개, 간선의 개수가 최대 4 * V이므로 1초 안에 처리 가능하다.

 

* 시작 지점인 1,1에 도로가 이미 존재하지 않는 경우를 고려하자.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, pair<int, int>> piii;
const int INF = 0x3f3f3f3f;

struct cmp {
	bool operator() (piii A, piii B) {
		return A.first > B.first;
	}
};

int M, N;
int city[1001][1001];
int dist[1001][1001];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void Dijkstra(int start_x, int start_y);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> M >> N;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cin >> city[i][j];
			if (city[i][j] == -1) city[i][j] = INF;
		}
	}
	Dijkstra(0, 0);
	if (dist[M - 1][N - 1] == INF) cout << -1;
	else cout << dist[M - 1][N - 1];
	return 0;
}

void Dijkstra(int start_x, int start_y) {
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) dist[i][j] = INF;
	}
	priority_queue <piii, vector<piii>, cmp> pq;
	dist[start_y][start_x] = city[start_y][start_x];
	pq.push({ city[start_y][start_x], {start_x, start_y} });
	while (pq.size()) {
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		int val = pq.top().first;
		pq.pop();
		if (dist[y][x] < val) continue;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			int new_val = val + city[ny][nx];
			if (dist[ny][nx] > new_val) {
				dist[ny][nx] = new_val;
				pq.push({ new_val, {nx,ny} });
			}
		}
	}
}