백준 16958 - 텔레포트

문제

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

리뷰

플로이드 워셜을 이용하여 풀이할 수 있는 문제였다.

우선 좌표 정보와 특별한 도시 여부를 표현하기 위한 Point 클래스를 정의하였다.
이후 입력시 이 Point 클래스를 통해 도시 정보들을 List에 저장하고 map을
초기화하는 initMap 메서드에선 두 도시 $i,j$에 대해 map[i][j]를 다음과 같이 설정한다.

• 두 도시가 모두 특별할때 : T와 두 도시간 이동 시간중 작은 것을 map[i][j]로 설정
• 그 외 : 도시간 이동 시간을 map[i][j]로 설정

이후, 플로이드 워셜을 통해 모든 도시간 최단 경로 비용을 구해 map에 저장한뒤 주어지는
M개의 쿼리에 답하면 된다.

로직의 시간복잡도는 플로이드 워셜의 $O(N^3)$으로 수렴하므로 최악의 경우 시간 초과가
떠야 맞지만 아마 언어에 따른 시간 보너스가 좀 여유롭게 주어진 유형인 것 같다.
찾아보니 보통 1초=1억(번의 연산)이 정론이나 단순 연산의 경우 1초=10억도 가능한 경우가
있다는 것 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    static int N, T;
    static int[][] map;

    static List<Point> points = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = parseInt(st.nextToken());
        T = parseInt(st.nextToken());
        map = new int[N + 1][N + 1];

        points.add(null);
        int x, y, special;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            special = parseInt(st.nextToken());
            x = parseInt(st.nextToken());
            y = parseInt(st.nextToken());

            points.add(new Point(x, y, special == 1));
        }

        initMap();
        floyd();

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

        int i, j;
        StringBuilder sb = new StringBuilder();
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            i = parseInt(st.nextToken());
            j = parseInt(st.nextToken());

            sb.append(map[i][j]).append("\n");
        }

        System.out.print(sb);
        br.close();
    }


    static void initMap() {
        Point p1, p2;
        int d;

        for (int i = 1; i < points.size() - 1; i++) {
            p1 = points.get(i);

            for (int j = i + 1; j < points.size(); j++) {
                if (i == j) continue;

                p2 = points.get(j);

                d = Math.abs(p2.y - p1.y) + Math.abs(p2.x - p1.x);

                if (p1.special && p2.special) {
                    map[i][j] = map[j][i] = Math.min(T, d);
                } else {
                    map[i][j] = map[j][i] = d;
                }
            }
        }
    }


    static void floyd() {
        for (int k = 1; k <= N; k++)
            for (int i = 1; i <= N; i++)
                for (int j = 1; j <= N; j++) {
                    if (map[i][k] == MAX_VALUE || map[k][j] == MAX_VALUE)
                        continue;

                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
    }

    static class Point {
        int x, y;
        boolean special;

        public Point(int x, int y, boolean special) {
            this.x = x;
            this.y = y;
            this.special = special;
        }
    }
}

결과