취미로 코딩하기

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

이번에 볼 문제는 백준 25189번 문제인 시니컬한 개구리이다.
문제는 아래 링크를 확인하자.

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

개구리가 모든 점프가능한 에지를 하나하나 그린다면 약 20억개의 에지를 생성하게 되어 메모리초과 또는 시간초과를 받게 될 것이다. 이를 대신할 방법을 생각해내야 한다.

개구리밥을 무시한 점프를 시니컬점프라 부르자.

예제 3과 같이 개구리가 전혀 움직이지 않는 경우를 제외하면, 가능한 모든 경로는 (출발점 - 시니컬점프를 할 노드), (시니컬점프), (시니컬점프 도착 노드 - 도착점)의 형태로 나타낼 수 있다. 굳이 시니컬점프를 이용할 필요가 없더라도 경로상의 정상적인 점프 하나를 시니컬점프로 대신했다고 생각한다면 모든 경로는 위와 같이 표현이 가능하는 것을 알 수 있다.

시니컬점프는 하나의 행에 걸쳐서 사용하거나 하나의 열에 걸쳐서 사용한다. 따라서 (출발점 - 행)의 최소 점프횟수와 (행-도착점)의 소 점프횟수, 그리고 (출발점 - 열)의 최소 점프횟수와 (열 - 도착점)의 최소 점프횟수를 이용해 출발점에서 시니컬점프를 한번 이용해 도착점으로 이동하는 최소 점프횟수를 구해 문제를 해결할 수 있다.

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

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

int Sr, Sc, Er, Ec;
int R, C;
int S, E;
vector<int> G[1000000];
vector<int> invG[1000000];
int sdist[1000000];
int edist[1000000];

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

void bfs() {
	memset(sdist, 0x3f, sizeof(sdist));
	queue<int> que; que.push(S);
	sdist[S] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& node : G[cur]) {
			if (sdist[node] < 0x3f3f3f3f) continue;
			sdist[node] = sdist[cur] + 1;
			que.push(node);
		}
	}
}

void invbfs() {
	memset(edist, 0x3f, sizeof(edist));
	queue<int> que; que.push(E);
	edist[E] = 1;
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& node : invG[cur]) {
			if (edist[node] < 0x3f3f3f3f) continue;
			edist[node] = edist[cur] + 1;
			que.push(node);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> R >> C;
	cin >> Sr >> Sc >> Er >> Ec;
	Sr--, Sc--, Er--, Ec--;
	S = Sr * C + Sc, E = Er * C + Ec;
	if (S == E) {
		cout << 0;
		return 0;
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			int cur = r * C + c;
			int x; cin >> x;
			if (r - x > -1) {
				int nxt = (r - x) * C + c;
				G[cur].emplace_back(nxt);
				invG[nxt].emplace_back(cur);
			}
			if (r + x < R) {
				int nxt = (r + x) * C + c;
				G[cur].emplace_back(nxt);
				invG[nxt].emplace_back(cur);
			}
			if (c - x > -1) {
				int nxt = r * C + (c - x);
				G[cur].emplace_back(nxt);
				invG[nxt].emplace_back(cur);
			}
			if (c + x < C) {
				int nxt = r * C + (c + x);
				G[cur].emplace_back(nxt);
				invG[nxt].emplace_back(cur);
			}
		}
	}
	
	bfs();
	invbfs();

	int ans = 0x3f3f3f3f;
	for (int r = 0; r < R; r++) {
		int mn1 = 0x3f3f3f3f, mn2 = 0x3f3f3f3f;
		for (int c = 0; c < C; c++) {
			int idx = r * C + c;
			mn1 = min(mn1, sdist[idx]), mn2 = min(mn2, edist[idx]);
		}
		ans = min(ans, mn1 + mn2 - 1);
	}

	for (int c = 0; c < C; c++) {
		int mn1 = 0x3f3f3f3f, mn2 = 0x3f3f3f3f;
		for (int r = 0; r < R; r++) {
			int idx = r * C + c;
			mn1 = min(mn1, sdist[idx]), mn2 = min(mn2, edist[idx]);
		}
		ans = min(ans, mn1 + mn2 - 1);
	}

	if (ans == 0x3f3f3f3f) cout << -1;
	else cout << ans;
}