백준 10568 - Wormholes

문제

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

리뷰

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

테스트 케이스는 케이스별로 행성은 p개의 이름과 3차원 좌표 형태의 위치,
w개의 행성 이름으로 주어지는 웜홀 정보(단방향임에 주의!)와 q개의
출발 행성, 도착 행성 이름으로 구성된 쿼리로 구성되어 있다.
각 케이스별로 쿼리에 대해 최단 경로 비용을 가까운 정수(int) 형태로 답하는
것이 조건이다.

우선 행성 이름과 인덱스를 매핑하기 위해 HashMap을 사용하였다. 또한,
행성의 좌표 정보를 저장하기 위해 Point 클래스를 새로 산정하였다.
입력 받은 좌표 정보를 바탕으로 플로이드 워셜에 활용할 map을 초기화하며
행성간 거리를 초기화해준 다음, 웜홀 정보를 입력받으며 해당하는 map[i][j]의
값을 0으로 갱신해준다. 이후, 플로이드 워셜을 통해 모든 행성간 최단 경로 비용을
map에 저장하고 그것을 이용해 답을 도출하였다.

문자열을 인덱스와 매핑하고 double 타입으로 연산과 정수형 변환을 수행하는
것이 로직을 구성함에 있어 좀 유의해야 부분이었던 것 같다.

로직의 시간복잡도는 플로이드 워셜의 $O(p^3)$으로 수렴하고, 이는 $p=60$인
최악의 경우에도 무난히 제한 조건 5초를 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static double[][] map;
    static HashMap<String, Integer> idxMap = new HashMap<>();

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

        int p, x, y, z, w, q, idx1, idx2;
        String planet1, planet2;

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

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int turn = 1; turn <= T; turn++) {
            p = parseInt(br.readLine());
            map = new double[p][p];

            for (int i = 0; i < p; i++) {
                st = new StringTokenizer(br.readLine());
                planet1 = st.nextToken();
                x = parseInt(st.nextToken());
                y = parseInt(st.nextToken());
                z = parseInt(st.nextToken());

                point = new Point(x, y, z);
                idxMap.put(planet1, i);
                points.add(point);
            }

            initMap(points);

            w = parseInt(br.readLine());
            while (w-- > 0) {
                st = new StringTokenizer(br.readLine());
                planet1 = st.nextToken();
                planet2 = st.nextToken();

                idx1 = idxMap.get(planet1);
                idx2 = idxMap.get(planet2);

                map[idx1][idx2] = 0;
            }

            floyd();

            q = parseInt(br.readLine());
            sb.append("Case ").append(turn).append(":\n");
            while (q-- > 0) {
                st = new StringTokenizer(br.readLine());
                planet1 = st.nextToken();
                planet2 = st.nextToken();

                idx1 = idxMap.get(planet1);
                idx2 = idxMap.get(planet2);
                sb.append("The distance from " + planet1 + " to " + planet2 + " is " + (int) Math.round(map[idx1][idx2]) + " parsecs.\n");
            }

            points.clear();
            idxMap.clear();
        }

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


    static void initMap(List<Point> points) {
        double w;

        for (int i = 0; i < points.size() - 1; i++)
            for (int j = i + 1; j < points.size(); j++) {
                w = getDist(points.get(i), points.get(j));

                map[i][j] = map[j][i] = w;
            }
    }

    static double getDist(Point p1, Point p2) {
        return Math.sqrt(
                Math.pow(p2.x - p1.x, 2) +
                        Math.pow(p2.y - p1.y, 2) +
                        Math.pow(p2.z - p1.z, 2)
        );
    }

    static void floyd() {
        for (int k = 0; k < map.length; k++)
            for (int i = 0; i < map.length; i++)
                for (int j = 0; j < map.length; j++) {
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
    }

    static class Point {
        int x, y, z;

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

}

결과