백준 1445번, 일요일 아침의 데이트 풀이

문제

백준 1445번

풀이

우선 순위를 "쓰레기로 차있는 칸을 적게 지나가는 것"(A)을 높게 주고, "인접한 면을 적게 지나가는 것"(B)을 낮게 줍시다.

데이터를 두개로 관리하면서 다익스트라를 돌려주면 풀 수 있습니다.

 

그런데, 재미있는 풀이가 있어서 다뤄보려고 합니다.

위에서 우선 순위를 A를 높게, B를 낮게 줬고, A의 경우에 드는 가중치(비용)을 $ cost(A) $, B를 $ cost(B) $라고 둡시다.

각 정점까지 오는데의 비용을 아무리 $ cost(B) $를 합해도 $ cost(A) $가 안되도록 $ cost(A) $의 값을 설정합시다.

이 문제에서 정점의 개수가 많아봐야 2500개이므로, $ cost(B) = 1$, $ cost(A) = 2500 $으로 둡시다.

인접한 면을 지날 때는 1을 더해주고, 쓰레기를 밟으면 2500을 더해주면서 다익스트라를 돌려주면 됩니다.

 

쓰레기를 밟은 경우, 인접한 면을 지난 경우가 정수 $ ans = dist[x][y] $에서 독립적으로 저장됨을 알 수 있습니다.

따라서, $ ans / 2500 $이 쓰레기를 밟은 경우, $ ans\ \%\ 2500 $이 인접한 면을 지난 경우가 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int grid[51][51];
int dist[51][51];

vector<pii> diff = {
		{1,  0},
		{-1, 0},
		{0,  1},
		{0,  -1}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	pii start, end;

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			char c;
			cin >> c;
			if (c == 'g') grid[i][j] = 1;
			if (c == 'S') start = {i, j};
			if (c == 'F') end = {i, j};
		}

	priority_queue<pair<int, pii>> pq;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dist[i][j] = 1e9;

	dist[start.first][start.second] = 0;

	pq.push({0, start});


	while (!pq.empty()) {
		auto top = pq.top();
		auto curr_cost = -top.first;
		auto xy = top.second;

		pq.pop();

		if (dist[xy.first][xy.second] < curr_cost) continue;

		for (const auto &c : diff) {
			int x = xy.first + c.first, y = xy.second + c.second;
			if (x < 1 || x > n || y < 1 || y > m) continue;
			int nxt = curr_cost;
			if (!grid[x][y])
				for (const auto &cc : diff) {
					int xx = x + cc.first, yy = y + cc.second;
					if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
					if (x == end.first && y == end.second) break;
					if (grid[xx][yy]) {
						++nxt;
						break;
					}
				}
			else nxt += 2500;

			if (dist[x][y] <= nxt) continue;

			dist[x][y] = nxt;
			pq.push({-nxt, {x, y}});
		}
	}

	cout << dist[end.first][end.second] / 2500 << " " << dist[end.first][end.second] % 2500;
}