도망자 원숭이
알고리즘 구분 : 그래프 이론, 플로이드 워셜
문제
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러나 그는 곧 동물원 직원에게 쫓기는 신세가 되었다. 원숭이와 동물원 직원사이에 쫓고 쫓기는 추격전을 살펴보자.
원숭이가 사는 나라는 여러 개의 도시와 도시들을 연결하는 길들로 구성되어 있다. 각 길들은 두 개의 도시를 양방향으로 연결한다. 또한, 각 길은 지나갈 때마다 일정한 시간이 걸린다. 원숭이는 시작도시에서 탈출하여 도착도시까지 최대한 빠른 시간에 가야한다.
그런데 원숭이의 오랜 숙적 멍멍이가 이를 갈며 원숭이를 기다리고 있었다. 멍멍이는 원숭이가 도망가는 경로 중 시작점과 도착점을 포함한 도시 중 한 군데에서 원숭이를 괴롭히기로 계획했다. 각 도시마다 구조가 다르기 때문에 멍멍이가 원숭이를 괴롭힐 수 있는 시간이 정해져있다.
그래서 멍멍이는 원숭이가 도망가는 경로 상에 있는 모든 도시들 중에서 가장 오랜 시간동안 괴롭힐 수 있는 도시에서 괴롭히기로 계획했다. 원숭이는 멍멍이를 피할 수 없다. 피할 수 없다면 즐겨라! 시작도시와 도착도시가 주어졌을 때, 원숭이가 최대한 빨리 도망갈 수 있는 시간을 구하는 프로그램을 작성하시오.
예를 들어, A, B, C, D 4개의 도시가 있고 원숭이는 A에서 도망쳐서 D로 가려고 한다고 하자. 이때, A-B와 B-D 간의 도로의 통행시간은 각각 50 이고 A-C 와 C-D 간의 도로의 통행시간은 각각 70 이면 A-B-D 의 경로가 더 이익이다. (각각 100 과 140 의 시간이 걸린다.)
그러나, 네 도시에서 멍멍이가 원숭이를 괴롭힐 수 있는 시간이 10, 80, 20, 10 이라면 A-C-D 를 통해 가는 것이 시간을 더 줄일 수 있는 방법이다. (A-B-D 의 경우 100+80 = 180 의 시간이 걸리고, A-C-D 의 경우 140+20 = 160 의 시간이 걸린다.)
입력
첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다.
그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴롭힐 수 있는 시간이 주어진다. 각 시간은 1이상 10,000이하의 정수이다. 그 후 M줄에 각각 3개의 정수로, 해당 도로가 잇는 두 도시의 번호 a, b (1 <= a, b <= N) 와 해당 도로의 통행시간 d 가 주어진다. 통행시간은 1이상 10,000이하의 정수이다.
그 후 Q줄에 각각 2개의 정수로, 원숭이의 출발도시와 도착도시 S, T 가 주어진다.
출력
첫째 줄에 원숭이가 S 번 도시로부터 T 번 도시까지 도망가는 데 드는 최소시간을 출력한다. 만약 두 도시 간에 경로가 없을 경우, -1 을 출력한다.
예제 입력 1
7 8 5
2 3 5 15 4 4 6
1 2 20
1 4 20
1 5 50
2 3 10
3 4 10
3 5 10
4 5 15
6 7 10
1 5
1 6
5 1
3 1
6 7
예제 출력 1
45
-1
45
35
16
문제 풀이
첫 번째 접근
문제의 특징 상, 플로이드 워셜이 분명하기에, 플로이드 워셜로 구현하였다.
여기서, 멍멍이가 괴롭히는 경우는 방문하는 정점 중 가장 오랜 시간동안 괴롭힐 수 있는 장소를 선택하게 되기에, 쟁점인 부분은 만약 val1 == val2인 상황에서 멍멍이가 괴롭히는 시간의 값이 큰 변수로 갱신해야하는가, 반대로 이동하는 거리가 큰 값일 경우의 변수로 갱신해야하는가였다.
결론적으로는 멍멍이가 괴롭히는 시간이 큰 변수로 갱신을 진행하도록 하여 플로이드 워셜 방식의 소스 코드를 구현하였으나 4%에서 WA를 받았다.
첫 번째 접근 소스 코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define INF 987654321
#define ll long long
int n, m, q;
ll bully[501];
pair<ll, ll> graph[501][501]; // first : 통행시간, second : 괴롭히는 Max 시간
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> q;
for(int i = 1; i < n + 1; i++) {
cin >> bully[i];
}
// graph 비용 {INF, INF}로 초기화
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j < n + 1; j++) {
graph[i][j] = {INF, INF};
}
}
for(int i = 0; i < m; i++) {
ll a, b, d, maxNum;
cin >> a >> b >> d;
maxNum = max(bully[a], bully[b]);
graph[a][b] = {d, maxNum}; // first : 거리, second : 멍멍이의 최대 괴롭힘 시간 갱신
graph[b][a] = {d, maxNum};
}
solve();
while(q--) {
int s, t;
cin >> s >> t;
if(graph[s][t].first == INF) {
cout << -1 << endl;
}
else {
cout << graph[s][t].first + graph[s][t].second << endl;
}
}
return 0;
}
void solve() {
for(int k = 1; k < n + 1; k++) {
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j < n + 1; j++) {
ll val1, val2;
val1 = graph[i][j].first + graph[i][j].second;
val2 = graph[i][k].first + graph[k][j].first + max(graph[i][k].second, graph[k][j].second);
if(val1 > val2) {
graph[i][j].first = graph[i][k].first + graph[k][j].first;
graph[i][j].second = max(graph[i][k].second, graph[k][j].second);
}
else if(val1 == val2) {
if(graph[i][j].second < max(graph[i][k].second, graph[k][j].second)) {
graph[i][j].first = graph[i][k].first + graph[k][j].first;
graph[i][j].second = max(graph[i][k].second, graph[k][j].second);
}
}
}
}
}
}두 번째 접근
결국 멍멍이가 괴롭히는 시간이 영향을 미치게 되므로, 삼중반복문의 가장 바깥의 반복문을 멍멍이가 괴롭히는 시간을 오름차순으로 정렬한 뒤, 그 순서에 맞추어서 경유지점으로 방문하면서 갱신하도록 진행하였다. 이 부분은 질문 게시판을 보고 접근할 수 있었다.
Q. 경유하는 점의 순서를 멍멍이가 괴롭히는 시간이 적은 순서부터 오름차순으로 정렬해어 접근해야 하는가?
A. 괴롭히는 시간이 적은 노드부터 경유한다면 괴롭히는 시간 + 이동시간이 최소가 되는 최단거리를 구할 수 있다. 즉, 시작 노드, 경유 노드, 도착 노드의 방해 정보만을 가지고 최단거리를 구할 수 있다는 의미이다.
즉, 가중치가 없는 경우에는 방문하는 노드의 순서가 중요하지 않으나, 가중치가 존재하는 유형의 플로이드일 경우, 해당 가중치가 가장 적은 노드부터 방문하도록 구현하여야 한다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define INF 987654321
#define ll long long
int n, m, q;
vector<pair<ll, ll>> bully;
pair<ll, ll> graph[501][501]; // first : 통행시간, second : 괴롭히는 Max 시간
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m >> q;
for(int i = 1; i < n + 1; i++) {
int input;
cin >> input;
bully.push_back({input, i});
}
// graph 비용 {INF, INF}로 초기화
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j < n + 1; j++) {
if(i == j) {
graph[i][j] = {0, bully[i - 1].first};
}
graph[i][j] = {INF, INF};
}
}
for(int i = 0; i < m; i++) {
ll a, b, d, maxNum;
cin >> a >> b >> d;
maxNum = max(bully[a - 1].first, bully[b - 1].first);
graph[a][b] = {d, maxNum}; // first : 거리, second : 멍멍이의 최대 괴롭힘 시간 갱신
graph[b][a] = {d, maxNum};
}
solve();
while(q--) {
int s, t;
cin >> s >> t;
if(graph[s][t].first == INF) {
cout << -1 << endl;
}
else {
cout << graph[s][t].first + graph[s][t].second << endl;
}
}
return 0;
}
void solve() {
// 정점 정렬
sort(bully.begin(), bully.end(), less<pair<ll, ll>>());
for(auto k : bully) {
for(int i = 1; i < n + 1; i++) {
for(int j = 1; j < n + 1; j++) {
ll val1, val2;
val1 = graph[i][j].first + graph[i][j].second;
val2 = graph[i][k.second].first + graph[k.second][j].first + max(graph[i][k.second].second, graph[k.second][j].second);
if(val1 > val2) {
graph[i][j].first = graph[i][k.second].first + graph[k.second][j].first;
graph[i][j].second = max(graph[i][k.second].second, graph[k.second][j].second);
}
else if(val1 == val2) {
if(graph[i][j].second < max(graph[i][k.second].second, graph[k.second][j].second)) {
graph[i][j].first = graph[i][k.second].first + graph[k.second][j].first;
graph[i][j].second = max(graph[i][k.second].second, graph[k.second][j].second);
}
}
}
}
}
}- 문제 출처 : https://www.acmicpc.net/problem/1602
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
