[BOJ/JAVA] 16958번: 텔레포트

16958번: 텔레포트

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

키워드

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

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

---

구현

• 두 도시 간 거리를 전부 계산하여 cityMatrix에 저장한다.

• 만약 두 도시가 특별한 도시라면 T와 비교하여 더 작은 시간을 저장한다.

• 플로이드-워셜 알고리즘을 이용하여 최소 이동 시간을 구하자.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class java_16958 {
    // N : 도시의 수
    // T : 텔레포트하는데 걸리는 시간
    static int N, T;

    static City cities[];

    static int cityMatrix[][];

    static class City {
        boolean isSpecial;
        int x, y;

        public City(boolean isSpecial, int x, int y) {
            this.isSpecial = isSpecial;
            this.x = x;
            this.y = y;
        }

        // 텔레포트를 고려한 거리 계산
        public int calcDistance(City target) {
            int distance = Math.abs(this.x - target.x) + Math.abs(this.y - target.y);

            // 텔레포트가 가능한 경우
            if (this.isSpecial && target.isSpecial) {
                return Math.min(distance, T);
            }

            // 텔레포트가 불가능한 경우 (해밀턴 거리 반환)
            return distance;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        cities = new City[N];
        cityMatrix = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            boolean isSpecial = Integer.parseInt(st.nextToken()) == 1 ? true : false;
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            City city = new City(isSpecial, x, y);
            cities[i] = city;
            Arrays.fill(cityMatrix[i], Integer.MAX_VALUE);
            cityMatrix[i][i] = 0;
        }

        // 거리 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cityMatrix[i][j] = cities[i].calcDistance(cities[j]);
                cityMatrix[j][i] = cities[i].calcDistance(cities[j]);
            }
        }

        // 최단거리 계산하기
        floydWarshall();

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int cityA = Integer.parseInt(st.nextToken()) - 1;
            int cityB = Integer.parseInt(st.nextToken()) - 1;

            System.out.println(cityMatrix[cityA][cityB]);
        }

        br.close();
    }

    private static void floydWarshall() {
        // i를 들려서
        for (int i = 0; i < N; i++) {
            // j에서
            for (int j = 0; j < N; j++) {
                // k를 가는 방법
                for (int k = 0; k < N; k++) {
                    if (j == k || k == i) {
                        continue;
                    }
                    // j->i->k 가는 거리 계산
                    // 거리 갱신
                    cityMatrix[j][k] = Math.min(cityMatrix[j][i] + cityMatrix[i][k], cityMatrix[j][k]);
                }
            }
        }
    }

}

---

Uploaded by N2T