백준 14611번, 월요병

 

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

14611번: 월요병

요약

 

(1,1) 지점에서 (M,N) 지점으로 이어지는 길이 없게끔 벽을 세운다.

---

1. 미리 정해진 지도의 상태가 주어진다. 이때, 벽이 이미 존재하는 장소, 비용을 지불하고 벽을 세울 수 있는 장소, 벽을 세울 수 있는 장소, 3가지로 분류된다.

 

2. (1,1) 지점에서 (M,N) 지점으로 이어지는 길이 없게끔 벽을 세우는 아이디어를 떠올려보자. 다음과 같은 좌표 평면을 살펴보자.

좌상단에서 우하단으로 향하는 길이 존재하지 않는다는 것은, 다음과 같이 벽이 존재한다는 것과 같다.

따라서, 문제를 바꾸어보자.
0행이나 M-1열 위에 존재하는 임의의 점에서 벽 위에서 이동하여 0열이나 N-1행 위에 존재하는 임의의 점으로 도달하게끔 벽을 세워보자.

벽을 위와 같이 대각선으로 이어지게 세우는 경우에도 길을 막을 수 있으므로, 이를 고려한다.

3. 벽이 이미 존재하는 장소의 비용을 0, 벽을 세울 수 없는 장소의 비용을 INF으로 설정하여 다익스트라로 풀이한다.

 

* 시작 지점과 도착 지점에 해당하는 정점이 한 곳이 아님에 유의하여 구현한다.

 

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

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

int N, M;
long long ans = INF;
long long village[301][301];
long long dist[301][301];
int dx[8] = { -1, -1, -1, 1, 1, 1, 0, 0 };
int dy[8] = { -1, 0, 1, -1, 0, 1, -1, 1 };

void Dijkstra();

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> village[i][j];
			if (village[i][j] == -2) village[i][j] = 0;
			if (village[i][j] == -1) village[i][j] = INF;
		}
	}
	Dijkstra();
	for (int i = 0; i < N; i++) ans = min(ans, dist[i][0]); // 0열에 도착
	for (int i = 0; i < M; i++) ans = min(ans, dist[N - 1][i]); // N-1행에 도착
	if (ans == INF) cout << -1;
	else cout << ans;
	return 0;
}

void Dijkstra() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) dist[i][j] = INF;
	}
	priority_queue<plii, vector<plii>, cmp> pq;
	for (int i = 0; i < M; i++) { // 0행에서 시작
		if (village[0][i] == INF) continue;
		pq.push({ village[0][i], {i, 0} });
		dist[0][i] = village[0][i];
	}
	for (int i = 0; i < N; i++) { // M-1열에서 시작
		if (village[i][M - 1] == INF) continue;
		pq.push({ village[i][M - 1], {M - 1, i} });
		dist[i][M - 1] = village[i][M - 1];
	}
	while (pq.size()) {
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		long long val = pq.top().first;
		pq.pop();
		if (dist[y][x] < val) continue;
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx > M - 1 || ny < 0 || ny > N - 1) continue;
			if (village[ny][nx] == INF) continue;
			long long new_val = val + village[ny][nx];
			if (dist[ny][nx] > new_val) {
				dist[ny][nx] = new_val;
				pq.push({ new_val, {nx,ny} });
			}
		}
	}
}