ALOHA 월반 3주차 - 최단 경로 (Dijkstra / Bellman-Ford / Floyd-Warshall)

1. [13549] 숨바꼭질 3 (Gold V)

의도한 태그: Dijkstra (Easy)

 

정점은 그냥 좌표고, 간선은 문제에서 충분히 자세히 알려주고 있습니다.

탐색 범위를 넉넉하게 잡는 걸 추천합니다. 저는 자세한 생각하기 귀찮아서 목적지에 2를 곱한 \( 200\,000 \)으로 잡았습니다.

const ll INF = 0x3f3f3f3f3f3f3f3f;

ll dis[200020];
ll djk(int st, int ed){
	memset(dis, 0x3f, sizeof(dis)); dis[st] = 0;
	priority_stack<pl2> pq; pq.push({0, st});
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		pq.pop();
		if (dst != dis[now]){ continue; }
		for (pl2 p : { mkp(now*2, 0), mkp(now+1, 01), mkp(now-1, 1) }){
			int nxt = p.fr; int d = p.sc;
			if (0 > nxt || nxt > 200000){ continue; }
			if (dis[nxt] <= dst+d){ continue; }
			dis[nxt] = dst+d; pq.push({dst+d, nxt});
		}
	}
	return dis[ed];
}

void Main(){
	int st, ed; cin >> st >> ed;
	cout << djk(st, ed);
}

사실 Well-known? 0-1 BFS로 더 맛있게 풀 수 있습니다.

코드는 귀찮으니까 나중에 짜야지

2. [2458] 키 순서 (Gold IV)

의도한 태그: Floyd-Warshall (Easy)

 

두 학생 \( v, w \)의 키를 비교할 수 있다면, \( v \)에서 \( w \)로의 (또는 그 반대 방향의) 경로가 존재해야 합니다.

그리고, 어떤 학생의 순위를 특정하기 위해서는, 다른 모든 학생들과 키를 비교할 수 있어야 합니다.

 

그러니, 플로이드를 돌려서 모든 \( v, w \)의 경로 존재 여부를 판별한 뒤,

다른 모든 학생들과의 경로가 존재하는 \( v \)의 개수를 세주면 됩니다.

bool adj[520][520];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ adj[i][i] = 1; }
	while (m--){
		int v, w; cin >> v >> w;
		adj[v][w] = 1;
	}
	for (int k = 1; k <= n; k++){
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++){
		bool res = 1;
		for (int j = 1; j <= n; j++){
			res = res && (adj[i][j] || adj[j][i]);
		}
		ans += res;
	}
	cout << ans;
}

3. [11657] 타임머신 (Gold IV)

의도한 태그: Bellman-Ford (Easy)

 

벨만 포드 구현 문제입니다.

 

저거 말고는 딱히 할 말이 없으니 자주 틀리는 부분 하나 놓고 가겠습니다.

음수 사이클의 판별에서 '1번 정점에서 닿을 수 없은 음수 사이클'을 잘못 판별하고 있는 건 아닌지 주의해주세요.

vector<pi3> edg;
const ll INF = 1e15; ll dis[520];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 2; i <= n; i++){ dis[i] = INF; }
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		edg.push_back({ {v, w}, x });
	}
	for (int t = 1; t <= n; t++){
		for (pi3 p : edg){
			int v = p.fr.fr, w = p.fr.sc, x = p.sc;
			if (dis[v] == INF){ continue; }
			if (dis[w] <= dis[v]+x){ continue; }
			dis[w] = dis[v] + x; if (t == n){ cout << -1; return; }
		}
	}
	for (int i = 2; i <= n; i++){
		cout << (dis[i] == INF ? -1 : dis[i]) << endl;
	}
}

4. [10159] 저울 (Gold III)

의도한 태그: Floyd-Warshall (Normal)

 

이 문제의 약화 버전인 2번 문제의 풀이를 먼저 읽고 오자.

이 문제의 풀이는 거기에 한 문장만 더 추가하면 된다.

 

각 물건별로, 무게를 비교할 수 없는 물건의 개수는 '그 물건까지의 경로가 존재하지 않는' 물건의 개수이다.

그러니 저걸 대신 세서 출력하면 된다.

bool adj[520][520];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ adj[i][i] = 1; }
	while (m--){
		int v, w; cin >> v >> w;
		adj[v][w] = 1;
	}
	for (int k = 1; k <= n; k++){
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++){
		int ans = 0;
		for (int j = 1; j <= n; j++){
			ans += !adj[i][j] && !adj[j][i];
		}
		cout << ans << endl;
	}
}

5. [1865] 웜홀 (Gold III)

의도한 태그: Bellman-Ford (Normal)

 

하지만 Floyd-Warshall로 푼다면 어떨까?

답은 굉장히 간단한데, 그냥 \( v \)에서 \( v \)로 가는 최단경로의 길이가 \( 0 \) 미만인지 판별하면 된다.

굉장히 정직하면서도 AC를 받아주는 착한 풀이다.

ll adj[520][520];

int main(){
	Fast;
	int t;
	cin >> t;
	while (t--){
		int n, m, w;
		cin >> n >> m >> w;
		for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) adj[i][j] = (i==j ? 0 : INF);
		while (m--){
			ll x, y, z;
			cin >> x >> y >> z;
			adj[x][y] = min(adj[x][y], z);
			adj[y][x] = min(adj[y][x], z);
		}
		while (w--){
			ll x, y, z;
			cin >> x >> y >> z;
			adj[x][y] = min(adj[x][y], -z);
		}
		for (int k = 1; k <= n; k++){
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= n; j++){
					adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
				}
			}
		}
		bool neg = false;
		for (int i = 1; i <= n; i++) neg = (neg || adj[i][i] < 0);
		cout << (neg ? "YES" : "NO") << endl;
	}
}

6. [9370] 미확인 도착지 (Gold II)

의도한 태그: Dijkstra (Hard)

 

예술가들은, 중간에 \( g \rightarrow h \)의 간선을 타고 지나갑니다.

그러니, 예술가들의 경로는 \( s \Rightarrow g \rightarrow h \Rightarrow e \) 또는 \( s \Rightarrow h \rightarrow g \Rightarrow e \)가 됩니다.

 

그러니, 각 후보지점 \( e \)에 대해서 위 경로의 길이와 \( s \Rightarrow e \)의 길이가 동일한지 보면 됩니다.

const ll INF = 1e15;
int n, m, k;
vector<pl2> adj[2020];
ll dis[3][2020];

void f(int st, int idx){
	for (int i = 1; i <= n; i++){ dis[idx][i] = INF; }
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		ll dst = pq.top().fr; int now = pq.top().sc;
		pq.pop();
		if (dst != dis[idx][now]){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[idx][nxt] <= d+dst){ continue; }
			dis[idx][nxt] = d+dst;
			pq.push({dis[idx][nxt], nxt});
		}
	}
}

void Main(){
	int t; cin >> t;
	while (t--){
		cin >> n >> m >> k;
		int st, x, y; cin >> st >> x >> y;
		ll d = 0;
		while (m--){
			int a, b, c; cin >> a >> b >> c;
			if (a==x && b==y || a==y && b==x){ d = c; }
			adj[a].push_back({b, c}); adj[b].push_back({a, c});
		}
		f(st, 0); f(x, 1); f(y, 2);
		vector<int> ans;
		while (k--){
			int a; cin >> a;
			if (dis[0][a] == dis[0][x] + d + dis[2][a] || dis[0][a] == dis[0][y] + d + dis[1][a]){ ans.push_back(a); }
		}
		sort( all(ans) );
		for (int x : ans){ cout << x << ' '; }
		cout << endl;
		for (int i = 1; i <= n; i++){ adj[i].clear(); }
	}
}

7. [2176] 합리적인 이동경로 (Gold I)

의도한 태그: Dijkstra (Normal)

 

\( T \)에 가까워지면서 이동한다는 건, \( T \)와의 거리가 점점 줄어든다는 의미입니다.

그러니, 모든 정점에서 \( T \)까지의 거리를 미리 찾은 뒤, 이를 토대로 아래 DP를 돌려주면 됩니다.

\( D_{v} = v \)에서 출발해서 \( T \)까지 가는 합리적인 이동경로의 개수

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<pl2> adj[1020];

ll dis[1020];
bool djk(int st){
	memset(dis, 0x3f, sizeof(dis)); dis[st] = 0;
	priority_stack<pl2> pq; pq.push({0, st});
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		pq.pop();
		if (dst != dis[now]){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; int d = p.sc;
			if (dis[nxt] <= dst+d){ continue; }
			dis[nxt] = dst+d; pq.push({dst+d, nxt});
		}
	}
	return dis[1] != INF;
}

ll dp[1020];
ll dpf(int now){
	if (dp[now] != -1){ return dp[now]; }
	if (now == 2){ return dp[now] = 1; }
	dp[now] = 0;
	for (pl2 p : adj[now]){
		int nxt = p.fr; if (dis[now] <= dis[nxt]){ continue; }
		dp[now] += dpf(nxt);
	}
	return dp[now];
}

void Main(){
	int n, m; cin >> n >> m;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	if( !djk(2) ){ cout << 0; return; }
	memset(dp, -1, sizeof(dp)); cout << dpf(1);
}

8. [19537] 전투 시뮬레이션 (Platinum V)

의도한 태그: Dijkstra (Hard)

 

사실 하라는 건 문제에 다 나와있습니다.

문제가 길고 구현할 게 많아서 그렇지...

굳이 풀이로 한 마디를 붙이자면... 이동 가능 여부를 '지날 수 있는 칸만 사용하는 최단경로'로 판별해주면 됩니다.

typedef pair<ll, pll> plll;
struct unit{ int hp, team, y, x; };

int mp[520][520];
int tck[2][520][520];
int d[10];
unit arr[250020];
int n, h, w;

inline bool f(int idx, int ey, int ex){
	//cout << "F " << idx << ' ' << ey << ' ' << ex << endl;
	priority_queue<plll, vector<plll>, greater<plll> > pq;
	bool chk[520][520] = {};
	pq.push({0, {arr[idx].y, arr[idx].x}});
	while (!pq.empty()){
		int dis = pq.top().fr, y = pq.top().sc.fr, x = pq.top().sc.sc;
		pq.pop();
		//cout << "PQ " << dis << ' ' << y << ' ' << x << endl;
		if (y == ey && x == ex) return true;
		if (chk[y][x]) continue;
		chk[y][x] = true;
		for (int k = 0; k < 4; k++){
			int yy = y+dy[k], xx = x+dx[k];
			//cout << endl;
			//cout << yy << ' ' << xx << ' ';
			if (1 > yy || yy > h || 1 > xx || xx > w) continue;
			//cout << "COND1 ";
			if (chk[yy][xx] || mp[yy][xx] == -1) continue;
			//cout << "COND2 " << mp[yy][xx] << ' ';
			if (dis+mp[yy][xx] > arr[idx].hp) continue;
			//cout << "COND3 ";
			if (tck[ arr[idx].team ^ 1 ][yy][xx] != 0 && (yy!=ey || xx!=ex)) continue;
			//cout << "COND4 ";
			//cout << "PUSH " << dis+mp[yy][xx] << ' ' << yy << ' ' << xx << endl;
			pq.push({dis+mp[yy][xx], {yy, xx}});
		}
	}
	return false;
}

inline void g(int team, int y, int x, int val){
	tck[team][y][x] += val;
	for (int k = 0; k < 4; k++){
		int yy = y+dy[k], xx = x+dx[k];
		if (1 > yy || yy > h || 1 > xx || xx > w) continue;
		tck[team][yy][xx] += val;
	}
}

void Main(){
	cin >> n >> h >> w;
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++){
			cin >> mp[i][j];
		}
	}
	for (int i = 1; i <= n; i++){
		cin >> d[i];
	}
	for (int i = 1; i <= h; i++){
		for (int j = 1; j <= w; j++){
			mp[i][j] = d[ mp[i][j] ];
		}
	}
	int m;
	cin >> m;
	for (int i = 1; i <= m; i++){
		cin >> arr[i].hp >> arr[i].team >> arr[i].y >> arr[i].x;
		arr[i].y += 1; arr[i].x += 1;
		g(arr[i].team, arr[i].y, arr[i].x, 1);
	}
	int q;
	cin >> q;
	while (q--){
		int u, y, x;
		cin >> u >> y >> x;
		y += 1; x += 1;
		bool chk = false;
		for (int i = 1; i <= m; i++){
			chk |= arr[i].y == y && arr[i].x == x;
		}
		if (chk) continue;
		if (f(u, y, x)){
			g(arr[u].team, arr[u].y, arr[u].x, -1);
			arr[u].y = y;
			arr[u].x = x;
			g(arr[u].team, arr[u].y, arr[u].x, 1);
		}
/*
		for (int i = 1; i <= h; i++){
			for (int j = 1; j <= w; j++){
				cout << tck[0][i][j] << ' ';
			}
			cout << endl;
		}
		cout << endl;
		for (int i = 1; i <= h; i++){
			for (int j = 1; j <= w; j++){
				cout << tck[1][i][j] << ' ';
			}
			cout << endl;
		}
		cout << endl;
*/
/*
		cout << "COOR" << endl;
		for (int i = 1; i <= m; i++){
			cout << arr[i].y - 1 << ' ' << arr[i].x - 1 << endl;
		}
*/
	}
	for (int i = 1; i <= m; i++){
		cout << arr[i].y - 1 << ' ' << arr[i].x - 1 << endl;
	}
}

추가 한 마디: 이거 누가 셋에 넣었음 :blobangry: (본인이 넣었음)

원래 코드 읽어보면서 마음에 안 드는 코드는 다시 짜서 넣는데

이건 마음에 안 들지만 다시 짜기도 싫어요 ㅋㅋ

9. [1854] K번째 최단경로 찾기 (Platinum IV)

의도한 태그: Dijkstra (Hard)

 

각 정점별로, \( K \)개의 최단 경로를 저장해가면서 다익스트라를 돌리면 됩니다.

네. 정말 저거만 하면 됩니다.

 

경로의 업데이트는 지금 보고 있는 경로가 \( K \)번째 안으로 들어가는지만 확인하면 됩니다.

그러니 경로의 길이를 저장하는 최대 힙을 하나 만들고, 그 안의 원소를 \( K \)개로 유지시키면서 비교해주면 됩니다.

const ll INF = 0x3f3f3f3f3f3f3f3f;

vector<pl2> adj[10020];
priority_queue<ll> dis[10020];
int cnt[10020];

void djk(int st, int k){
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, 1}); dis[st].push(0);
	//cout << "HUH" << endl << flush;
	while (!pq.empty()){
		int now = pq.top().sc; ll dst = pq.top().fr;
		//cout << "PQ " << now << ' ' << cnt[now] << " = " << dst << endl << flush;
		pq.pop();
		cnt[now] += 1; if (cnt[now] > k){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[nxt].size() == k && dis[nxt].top() <= dst+d){ continue; }
			pq.push({dst+d, nxt});
			dis[nxt].push(dst+d); if (dis[nxt].size() > k){ dis[nxt].pop(); }
		}
	}
}

void Main(){
	int n, m, k; cin >> n >> m >> k;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x});
	}
	djk(1, k);
	for (int i = 1; i <= n; i++){
		if (dis[i].size() < k){ cout << -1; } else{ cout << dis[i].top(); }
		cout << endl;
	}
}

10. [23258] 밤편지 (Gold I)

의도한 태그: Floyd-Warshall (Additional)

 

플로이드 와샬에 대한 깊은 이해로 풀 수 있습니다.

 

플로이드 와샬에 대한 명확한 정의는 아래와 같은 DP입니다.

\( D_{v, w, k} = v \)에서 \( w \)로 가는 최단 경로. 단, 중간에 타는 정점의 번호는 \( k \)보다 작거나 같아야 한다.

그리고 이 DP의 초항과 점화식은 아래와 같습니다.

\( D_{v, w, 0} = adj[v][w] \) (중간에 지나는 정점이 없어야 하므로, 그냥 그래프 그대로 들고 오면 된다.)

\( D_{v, w, k} = \min(D_{v, w, k-1}, D_{v, k, k-1} + D_{k, w, k-1}) \) (각각 \( k \)번 정점을 지날 때와 지나지 않을 때이다.)

 

그럼 이걸로 문제를 어떻게 풀까요?

이슬을 \( 2^C \)방울 이상 마실 수 없다는 건 번호가 \( C \) 이상인 정점을 지날 수 없다와 동치입니다.

(\( 2^N > 2^{N-1} + 2^{N-2} + \ldots 2^1 + 2^0 \)이기 때문입니다. 이진수로 나타내면 이해가 쉬울 거에요.)

그러니, \( k, v, w \)로 들어오는 쿼리는 \( D_{v, w, k-1} \)로 처리해줄 수 있습니다.

 

그러니 플로이드 와샬의 중간과정을 다 저장하면서 돌려주면 문제를 풀 수 있습니다.

const ll INF = 1e15;
ll dis[302][302][302];

void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			cin >> dis[0][i][j];
			if (dis[0][i][j] == 0 && i != j){ dis[0][i][j] = INF; }
		}
	}
	for (int k = 1; k <= n; k++){
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				dis[k][i][j] = min(dis[k-1][i][j], dis[k-1][i][k] + dis[k-1][k][j]);
			}
		}
	}
	while (q --> 0){
		int st, ed, k; cin >> k >> st >> ed;
		if (dis[k-1][st][ed] == INF){ cout << -1 << endl; }
		else{ cout << dis[k-1][st][ed] << endl; }
	}
}