BOJ 35002 검은칠된 격자에 보내는 최단경로

문제 링크입니다.

문제 요약

격자에서 특정 두 칸 사이의 최단 경로가 $D$가 되도록 각 칸에 $0$ 이상 $9$ 이하의 가중치를 부여하세요.

풀이

가중치를 부여할 수 있는 모든 칸에 $0$을 부여했을 때 최단 경로가 가장 짧고, $9$를 부여했을 때 최단 경로가 가장 깁니다. 나아가 어떤 격자에서 임의의 칸의 가중치를 $1$ 올릴 때마다 최단 경로의 길이는 $1$ 증가하거나 유지됩니다.

이로부터, 부여한 가중치의 합으로 이분 탐색을 수행하면서 가중치를 임의로 배분해도 답이 존재한다면 항상 찾을 수 있음이 보장됩니다. 가중치 합에 맞게 적당히 가중치를 배분하고 다익스트라나 다이얼을 돌려 최단 경로를 찾아 나가면 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int dy[] = {-1,1,0,0}, dx[] = {0,0,-1,1};
char a[777][777], b[777][777]; int d[777][777], tot, sy, sx, ey, ex, k, n, m;

void build(int x){
	int offset = x/tot; x %= tot;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){b[i][j] = a[i][j]; if(b[i][j] == '.') b[i][j] = '0'+offset+(x-->0);}
}

int bfs(){
	queue<pii> q[10]; auto qsize = [&](){int ret = 0; for(int i = 0; i < 10; i++) ret += q[i].size(); return ret;};
	int idx = b[sy][sx]-'0'; q[idx].emplace(sy, sx); memset(d, 15, sizeof(d)); d[sy][sx] = idx;
	while(qsize()){
		while(q[idx].size()){
			auto [y, x] = q[idx].front(); q[idx].pop();
			if(d[y][x]%10 != idx) continue;
			for(int dir = 0; dir < 4; dir++){
				int ny = y+dy[dir], nx = x+dx[dir];
				if(b[ny][nx] == '#') continue;
				if(d[ny][nx] > d[y][x]+b[ny][nx]-'0'){
					d[ny][nx] = d[y][x]+b[ny][nx]-'0';
					q[d[ny][nx]%10].emplace(ny, nx);
				}
			}
		}
		idx++; idx %= 10;
	}
	return d[ey][ex];
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false); memset(a, '#', sizeof(a)); memset(b, '#', sizeof(b));
	cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){cin >> a[i][j]; if(a[i][j] == '.') tot++;}
	cin >> sy >> sx >> ey >> ex >> k;
	int l = 0, r = tot*9;
	while(l < r){build(mid); if(bfs() < k) l = mid+1; else r = mid;}
	build(mid); if(bfs() != k) return !(cout << -1);
	for(int i = 1; i <= n; i++, cout << '\n') for(int j = 1; j <= m; j++) cout << b[i][j];
}