[BOJ] 백준 14461. 소가 길을 건너간 이유 7 (Gold II)

최근에 ucpc, koi, usaco 등 대회 문제 질이 좋음을 깨달았다.

그래서 대회 문제를 풀어보던 중 맨날 

'농부 john', 'farmer john', '소가 길을 건너는 이유' 등의 주제로 농부 문제를 내는 문제가 있음을 알게 되고 풀어본 문제이다.

 

이 문제는 처음엔 굉장히 쉬운 dp, dijkstra, bfs문제인 줄 알았으나,

dp, bfs로는 풀 수가 없다.

그 이유는 아래와 같다.

 

1. bfs로 풀기에는 각각의 길에 가중치가 있다.
2. dp로 풀기에는 각각의 풀숲을 몇 번째에 지났는지에 따라 중복돼서 이용될 수가 있다.

사실 맨처음에는 dp로 풀 수 있지 않을까 생각했다.

bfs는 사실 처음엔 생각나지 않았다. (이건 bfs를 많이 풀어보면 느낄 것이다. 가중치가 있으면 dijkstra, 가중치가 같으면 bfs로 푸는 건 국룰이지 않을까)

www.acmicpc.net/board/view/23960

글 읽기 - dp인데 대체 어디가 문제인지 모르겠습니다

처음엔 이게 무슨 소린가 했는데,

이 질문 답변의 의도를 파악하지 못했다면

예제 입력 1의 답이 102가 나올 가능성이 매우 높다.

---

의식의 흐름 및 해설

사실 처음엔 bfs나 dp를 의심했으나, bfs는 바로 생각 내에서 지울 수 있었다.

각각의 칸을 이동하는 데에 2만큼의 가중치를 든 다해도, 각 칸마다 가중치가 다르기 때문에 bfs로 하면 queue에 저장되는 원소가 의도치 않게 될 수 있다는 점을 파악할 수 있었다.

그럼 이제 dijkstra나 dp 두 가지 대안이 남아있는데,

 

사실 나는 맨 처음에 dp로 접근했다.

그런데 이 문젠, 어느 칸에 최소의 시간으로 이만큼 접근한다 해도, 최종 목적지까지 최소의 시간이 아닐 수도 있다. 

예를 들어, 현재 칸까지 5번 이동하여 풀을 먹지 않아도 되는 상황인데, 최종 목적지까진 6번 이동하여 최종 목적지의 풀을 먹는 시간을 다 소모하는 경우, 오히려 최악의 답안을 낼 수도 있기 때문이다.

따라서 이 문제는 dijsktra의 응용으로 최선의 경우를 queue에 집어넣는 greedy 방식을 버리고 차선책의 방법을 택하는 방안으로 가야 한다.

 

예제 입력 1이 102의 답을 냈다면 충분히 공감이 갈 것이다.

2행 3열의 답이 21이 나왔을 것이다.

나 또한 그러한 실수를 했기 때문에 충분히 이해가 간다.

 

그러나, 현재 풀숲에 몇 번째에 도착했는지에 따라 현재 칸은 최악의 경우가 될 수도 있고 최선의 경우가 될 수도 있다.

예를 들어 현재 경우의 수가 최선이지만 5번째에 도착했다고 치고, 다른 경우의 수가 차선이지만, 6번째에 도착했다고 치자. 이 경우, 도착지점의 풀을 먹는 시간이 INF라 치면, 전자의 경우 최악의 답안을 내게 될 것이다.

 

이러한 경우 때문에 평범한 dijkstra로는 풀 수가 없다.

다만, 정말 중요한 키포인트인데,

(몇 번째에 도달했는지)%3이 같으면 평소와 같은 dijkstra로 풀 수 있다.

cost 외에도 다른 변수 원인이 있는 경우, 몇 번째에 도달했는지에 따라 여러 경우가 달라짐을 파악하고,

도착점에 도달했을 때엔 어차피 최소치에서 최소로 갱신된 것이므로 바로 답을 return해주면 그 때의 return값이 답임을 알 수 있을 것이다. (솔직히 술 마신 채로 포스팅하는 상태라서 제대로 이해가게 쓴 글인지 잘 모르겠다..^^.....)

 

 

따라서 이 경우는 일반적인 dijkstra가 아닌, 각각의 경우를 visit했으면 더 이상 그 경우를 처리하지 않는 방식으로만 접근해도 괜찮다. 즉, 일반적인 dijkstra보다 작은 부분집합의 예외처리를 하여 시간복잡도를 포기하는 대신(사실 그렇게 큰 시간복잡도 손해도 아니긴 하다) 더 정확한 답을 구해내는 것이다.

왜냐? 항상 cost가 작은 greedy스러운 방법으론 최적해를 구하지 못하기 때문이다.

 

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <cmath>
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef pair<pair<int, int>, int> pi;
const int INF = 1e9 + 7;
const int MAX = 101;
int a[MAX][MAX], N, T, ans, d[10001];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
bool visit[MAX][MAX][3];
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> T;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a[i][j];
			d[i * N + j] = INF;
		}
	}
	priority_queue<pi, vector<pi>, greater<pi>> pq;
	d[0] = 0;
	pq.push({ { 0, 0 }, 0 });
	while (!pq.empty()) {
		int idx = pq.top().first.second;
		int cur = pq.top().second;
		int y = cur / N;
		int x = cur % N;
		int cost = pq.top().first.first;
		pq.pop();
		if (visit[y][x][idx % 3])
			continue;
		visit[y][x][idx % 3] = true;
		d[cur] = min(d[cur], cost);
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
				int next = ny * N + nx;
				int nCost = cost + T;
				if (idx % 3 == 2)
					nCost += a[ny][nx];
				pq.push({ {nCost, idx + 1}, next });
			}
		}
	}
	cout << d[N * N - 1] << "\n";
}

생각해보니까 x, y 나눌 필요가 없었다...

다만 내가 항상 가중치를 포함하는 배열인 d를 사용해왔기 때문이고,

visit배열로 방문처리를 체크하는 dijkstra는 처음 짜봤기 때문에

이러한 코드가 나온게 아닌가싶다.

 

방문을 몇 번째로 했는지에 따라 가중치가 달라지기 때문에

일반적인 dijkstra로는 불가능한 문제였다.

방문을 몇번째에 했는지에 따라 이후 방문한 시간이 달라지기 때문에 

조건을 잘 설정해야 되는 문제였다.