[BOJ/Gold 1] 백준 23258 밤편지(C++)

문제 링크

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

23258번: 밤편지

 

문제

이 밤 그날의 반딧불을

당신의 창 가까이 보낼게요

사랑한다는 말이에요

- 아이유, 밤편지 中

선린마을에는 밤마다 소중한 사람을 향해 반딧불을 보내는 전통이 있다.

선린마을은 1번부터 N번까지의 번호가 붙은 N채의 집과 집 사이를 잇는 양방향 도로로 이루어져 있다. 반딧불은 출발지와 도착지를 직접 연결하는 길이 없거나 더 효율적인 경로가 있는 경우 다른 집들을 거쳐갈 수 있다. X번 집에는 2^X 방울의 이슬이 있으며, 반딧불은 출발지와 도착지를 제외하고 이동하는 동안 거치는 모든 집의 이슬을 반드시 모두 마셔야 한다. 안타깝게도 반딧불은 각각 상수 C를 가지고 있으며, 이슬을 2^C 방울 이상 마시면 더 이상 날아가지 않고 잠들어 버린다.

선린마을의 주민 찬우는 이슬을 2^C 방울 이상 마실 수 없는 반딧불이 S번 집에서 E번 집으로 이동하는 데 걸리는 최소 시간이 Q번이나 궁금해졌다.

찬우의 질문에 답하는 프로그램을 작성하자.

입력

첫째 줄에 집의 수 N과 질문의 수 Q가 주어진다. 

둘째 줄부터 N줄에 걸쳐 길의 정보가 주어진다. i번 줄의 j번째 수를 Di,j라고 할 때, Di,j가 양의 정수라면 i번 집과 j$j$번 집을 잇는 길을 통과하는 시간을 의미하고, 0이라면 i번 집과 j번 집 사이를 연결하는 길이 없다는 의미이다. 

다음 줄부터는 Q$개의 줄에 걸쳐 정수 C, S, E가 공백으로 구분되어 주어진다. 

이는 이슬을 2^C 방울 이상 마실 수 없는 반딧불이 S번 집에서 E번 집으로 이동하는 데 걸리는 최소 시간을 묻는 질문이다.

출력

 Q개의 줄에 걸쳐 질문의 답을 한 줄에 하나씩 순서대로 출력한다. 목적지에 도착하는 것이 불가능한 경우에는 -1을 출력한다.

제한

•  2≤N≤300
•  1≤i,j≤N인 모든 i, j에 대해 0≤Di,j≤170324, Di,j=Dj,i, Di,i=0
•  1≤Q≤500000
•  1≤S,E≤N
•  1≤C≤N+1

예제 입력 1

4 2
0 100 1 0
100 0 0 100
1 0 0 1
0 100 1 0
3 1 4
2 4 1

예제 출력 1

200
-1

 C=3일 때,  1번 정점에서 4번 정점으로 가는 경로 중 3번 정점을 지나는 경로는 반딧불이 3번 정점에서 8방울의 이슬을 마시고 잠들어버리기 때문에 불가능하다. 따라서 가능한 경로는 2번 정점을 거치는 경로뿐이다.

1번 정점에서 4번 정점으로 가려면 2번 혹은 3번 정점을 반드시 거쳐야 하므로, C=2일 때는 4번 정점에서 1번 정점으로 갈 수 없다.

알고리즘 분류

• 다이나믹 프로그래밍
• 최단 거리 알고리즘

풀이

3차원 배열로 시도했지만 잘 되지 않아 이 글을 참고하였다.

백준 23258 자바 - 밤편지 (BOJ 23258 JAVA)

1. 이슬을 2^C방울 이상 마시면 안 된다는 뜻은 반드시 출발지와 도착지를 제외하고 C번 미만의 집으로만 이동해야 한다는 뜻이다.

2. 플로이드-와샬의 개념을 생각해보면, i번에서 j번으로 가는 데 i->j가 더 빠른가, 아니면 i->k->j가 더 빠른가를 기록하는 것이다. 즉 k가 경유지이다. 이것을 확장하여, Cost[i][j][k]라는 3차원 배열로 최단 거리를 구하여, k번 이하의 방만을 경유해서 i부터 j까지 가는 최단 거리를 기록한다.

 

플래급은 되어 보이는데 왜 골드1인지 모르겠다. 플로이드-와샬의 개념을 다시 파악하는 데 큰 도움이 되었다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 301
#define LL long long
#define INF 1e9

using namespace std;
int N, Q;
int Cost[MAX][MAX][MAX]; // Cost[A][B][C] = A에서 B까지, C 이하의 경유지만을 거쳐서 이동한 최단 거리

/*
	이슬을 2^C방울 이상 마시면 안 됨 == 반드시 C - 1번 이하의 집을 통해서만 이동 가능함.(출발지와 도착지는 상관X)
*/

void Input() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> Cost[i][j][0];
			if (i == j) {
				continue;
			}
			if (Cost[i][j][0] == 0) {
				Cost[i][j][0] = INF;
			}
		}
	}
}

void Settings() {
	// C를 경유해서 i, j로 간 경우에 대한 중간과정을 모두 저장
	for (int C = 1; C <= N; C++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				Cost[i][j][C] = min(Cost[i][j][C - 1], Cost[i][C][C - 1] + Cost[C][j][C - 1]);
			}
		}
	}
}

void Query() {
	for (int i = 0; i < Q; i++) {
		int C, S, E;
		cin >> C >> S >> E;
		if (Cost[S][E][C - 1] == INF) {
			cout << -1 << "\n";
		}
		else {
			cout << Cost[S][E][C - 1] << "\n";
		}
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Query();

	return 0;
}