[BOJ] 백준 1602번 : 도망자 원숭이 (JAVA)

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러나 그는 곧 동물원 직원에게 쫓기는 신세가 되었다. 원숭이와 동물원 직원사이에 쫓고 쫓기는 추격전을 살펴보자.

 

원숭이가 사는 나라는 여러 개의 도시와 도시들을 연결하는 길들로 구성되어 있다. 각 길들은 두 개의 도시를 양방향으로 연결한다. 또한, 각 길은 지나갈 때마다 일정한 시간이 걸린다. 원숭이는 시작도시에서 탈출하여 도착도시까지 최대한 빠른 시간에 가야한다.

 

그런데 원숭이의 오랜 숙적 멍멍이가 이를 갈며 원숭이를 기다리고 있었다. 멍멍이는 원숭이가 도망가는 경로 중 시작점과 도착점을 포함한 도시 중 한 군데에서 원숭이를 괴롭히기로 계획했다. 각 도시마다 구조가 다르기 때문에 멍멍이가 원숭이를 괴롭힐 수 있는 시간이 정해져있다.

 

그래서 멍멍이는 원숭이가 도망가는 경로 상에 있는 모든 도시들 중에서 가장 오랜 시간동안 괴롭힐 수 있는 도시에서 괴롭히기로 계획했다. 원숭이는 멍멍이를 피할 수 없다. 피할 수 없다면 즐겨라! 시작도시와 도착도시가 주어졌을 때, 원숭이가 최대한 빨리 도망갈 수 있는 시간을 구하는 프로그램을 작성하시오.

 

예를 들어, 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차원 배열에 저장해 놓습니다.

 

이제, 플로이드 와샬 알고리즘을 수행합니다.

최단거리 배열은 원래 하던대로 전형적인 방식대로 값을 초기화하면 됩니다.

 

하지만, 패널티 시간을 고려한 배열을 초기화하는 과정이 중요했습니다.

출발점에서 끝점을 이동한 경로 상에서 패널티 시간이 가장 큰 하나의 도시만을 선택하여 최단거리에다가 이 시간을 더해 주어야한다는 점을 명심하시길 바랍니다.

 

그렇다면, 패널티 시간을 '어떻게' 더해주어야 할까요?

바로, 거쳐가는 정점을 패널티 시간이 적은 도시 순서대로 설정해 주는 것입니다.

 

패널티 시간이 큰 순서가 아닌 적은 순서대로 사용하는 이유는 아래 글을 참조하시길 바랍니다.

 

 

글 읽기 - 풀긴 풀었는데요..

 

 

이후, (최단거리 + 패널티 시간) 배열의 값은 위에서 구한 최단거리 값에다가 i, k, j 중 가장 큰 패널티 시간을 더해주면 됩니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
 
        int[][] dist = new int[N + 1][N + 1]; // 개를 배제한 최단거리 시간
        int[][] cost = new int[N + 1][N + 1]; // 개를 포함한 최단거리 시간
        int[] dog = new int[N + 1];
        Integer[] lowDogTimeArr = new Integer[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            dog[i] = Integer.parseInt(st.nextToken());
            lowDogTimeArr[i] = i;
        }
 
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dist[i][j] = (i == j) ? 0 : INF;
                cost[i][j] = (i == j) ? dog[i] : INF;
            }
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
 
            dist[a][b] = dist[b][a] = d;
            cost[a][b] = cost[b][a] = d + Math.max(dog[a], dog[b]);
        }
 
        // 개한테 방해받는 시간이 적은 도시 순서대로 정렬
        Arrays.sort(lowDogTimeArr, 1, N + 1, new Comparator<Integer>() {
 
            @Override
            public int compare(Integer arg0, Integer arg1) {
                return dog[arg0] - dog[arg1];
            }
 
        });
 
        // 플로이드 와샬 알고리즘
        int idx = -1;
        for (int k = 1; k <= N; k++) {
            // 거쳐가는 정점을 개한테 방해받는 시간이 적은 도시 순으로 설정
            idx = lowDogTimeArr[k];
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dist[i][idx] != INF && dist[idx][j] != INF) {
                        // 일반적인 최단거리 초기화 식
                        if (dist[i][j] > dist[i][idx] + dist[idx][j]) {
                            dist[i][j] = dist[i][idx] + dist[idx][j];
                        }
 
                        // 위에서 i, k, j 중 개한테 방해받는 시간이 가장 긴 정점을
                        // 기준으로 비용에 시간을 추가로 더해 줌.
                        if (cost[i][j] > dist[i][j] + Math.max(dog[i], Math.max(dog[idx], dog[j]))) {
                            cost[i][j] = dist[i][j] + Math.max(dog[i], Math.max(dog[idx], dog[j]));
                        }
                    }
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            sb.append(((cost[a][b] == INF) ? "-1" : cost[a][b]) + "\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
}
 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.