[자바]백준 16958번 텔레포트 [그래프 - 플로이드 워셜][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

 

문제

2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.

두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.

입력

첫째 줄에 도시의 수 N, 텔레포트하는데 걸리는 시간 T가 주어진다.

둘째 줄부터 N개의 줄에 도시의 정보를 의미하는 세 정수 s, x, y가 1번 도시부터 N번 도시까지 순서대로 주어진다. s가 1인 경우에는 특별한 도시라는 의미이고, 0인 경우는 특별한 도시가 아니라는 의미이다. (x, y)는 도시의 좌표이다.

다음 줄에는 M이 주어지고, 다음 M개의 줄에는 두 도시 A와 B가 주어진다. 

출력

총 M개의 줄에 걸쳐서 A에서 B에 가는 최소 이동 시간을 출력한다.

 

제한

• 2 ≤ N ≤ 1,000
• 1 ≤ T ≤ 2,000
• 1 ≤ M ≤ 1,000
• 0 ≤ x, y ≤ 1,000
• A ≠ B
• 두 도시의 좌표가 같은 경우는 없다.

 

예제 입력 1 

6 3
0 1 2
0 5 1
1 3 3
1 1 5
0 3 5
1 7 5
5
1 2
1 5
1 6
3 4
4 2

예제 출력 1

5
5
6
3
7

 

예제 입력 2

6 2
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
6
1 2
2 3
3 4
4 5
5 6
6 1

예제 출력 2

1
1
2
1
1
2

 

 

알고리즘 분류

• 그래프 이론
• 브루트포스 알고리즘
• 기하학
• 플로이드-워셜

 

문제 설명

해당 문제는 각각의 도시들에서 각각의 도시들로 이동시 최소 이동시간을 구하는 문제다.

특별한 도시는 특별한 도시로 텔레포트할 수 있다. 그렇다면 특별한 도시에서 특별한 도시로 이동하는 경우에는 텔레포트의 시간과 그냥 걸어서 가는 시간 중 작은 시간으로 계산하면 된다.

 

해설1 (생략 가능)

이 문제는 최소 이동시간을 구하는 문제다.

최소 이동 시간을 구하는 알고리즘은 다익스트라(다이크스트라), 벨만 포드, 플로이드 워셜 3가지가 있다.

이 중에서 이 문제에서 원하는 각각의 도시들에서 각각의 도시들 즉, 출발 지점과 도착 지점이 정해져 있지 않고 모든 도시들에서 모든 도시까지의 최소 이동 시간을 알고 싶은 경우는 플로이드 워셜뿐이다.

이 문제에 대해서 검색해 보면  시뮬레이션이라는 알고리즘을 사용해서 풀 수도 있다.
시뮬레이션 알고리즘으로 풀면 플로이드 워셜보다 10배 가량은 빠른 시간을 보였다.

 

시뮬레이션이라는 알고리즘은 추후에 공부하고 올리도록하고 지금은 플로이드 워셜로 풀어 보았다.

 

해설2 

각각의 도시들의 좌표가 순서대로 나오는데, 지문에서 말했듯 각각의 도시들의 이동시간은 |r1 - r2| + |c1 - c2|으로 나타낸다.

아래 순서대로 접근하는 게 좋은 것 같다고 생각한다.

1. 우선 각 도시들 데이터 담기
2. 모든 도시들과 모든 도시들의 이동시간을 다 구해준다.
3. 이동시간을 구할때는 특별한 도시끼리는 텔레포트시간과 이동시간 거리 중 작은 시간으로 잡아준다.
4. 플로이드 워셜 알고리즘을 사용해 각 도시에서 도시마다의 최소 이동 시간을 구해준다.
5. 출력

여기서 2번만 부가 설명을 하자면 1번 도시부터 5번 도시까지 있다면,

 

1번은 2번, 3번, 4번, 5번
2번은 3번, 4번, 5번

3번은 4번, 5번

4번은 5번

 

위의 방식대로만 구해주면 된다. 자세한건 아래 코드에서 setTimes() 부분을 보면 좋다.

 

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int n; // 도시 수
    static int t; // 텔레포트 시간
    static int[][] point;
    static int[][] times;
    static int INF = 1_000_000_001;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        point = new int[n + 1][3];
        
        // 각 도시들 데이터 초기화
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int isTel = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            point[i][0] = x;
            point[i][1] = y;
            point[i][2] = isTel;
        }

        times = new int[n + 1][n + 1];
        
        // 플로이드 워셜 알고리즘
        floydWarshall();

        int m = Integer.parseInt(br.readLine());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            bw.write(times[x][y] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    public static void floydWarshall() {
        // 모든 도시들과 모든 도시들의 이동시간 초기화
        setTimes();

        // 플로이드 워셜 알고리즘으로 도시마다 최소 이동시간을 구해줌
        for (int k = 1; k < n + 1; k++) {
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < n + 1; j++) {
                    if (times[i][k] != INF && times[k][j] != INF) {
                        times[i][j] = Math.min(times[i][j], times[i][k] + times[k][j]);
                    }
                }
            }
        }
    }

    public static void setTimes() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    times[i][j] = INF;
                }
            }
        }

        // 이부분이 각 도시들간의 이동시간 초기화 부분
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                times[i][j] = times[j][i] = Math.abs(point[i][0] - point[j][0]) +
                        Math.abs(point[i][1] - point[j][1]);

                if (point[i][2] == 1 && point[j][2] == 1) {
                    times[i][j] = times[j][i] = Math.min(times[i][j], t);
                }
            }
        }
    }
}