[백준] 16958 텔레포트 - Brute Force / Java

• 문제 링크

16958번: 텔레포트

 

• 풀이 과정

2차원 배열에 도시의 속성과 좌표를 입력받아 저장한다.

 

각 도시 간 이동시간을 구한 후, (Math.abs(map[i][1] - map[j][1]) + Math.abs(map[i][2] - map[j][2]))

두 도시가 특별한 도시일 경우 (map[i][0] + map[j][0] == 2)

해당 이동 시간과 텔레포트에 걸리는 시간 t 와 비교해 작은 값으로 저장한다.

 

이 후 플로이드 워셜 알고리즘을 통해 각 도시 간 최단 경로를 구하여 값을 갱신한 후,

 

추가로 입력받은 각각의 도시 간 좌표에 해당하는 최소 이동 시간 값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws 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 t = Integer.parseInt(st.nextToken());

        int[][] map = new int[n + 1][3];
        int[][] dist = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            map[i][0] = Integer.parseInt(st.nextToken());
            map[i][1] = Integer.parseInt(st.nextToken());
            map[i][2] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)
                    continue;

                int gap = Math.abs(map[i][1] - map[j][1]) + Math.abs(map[i][2] - map[j][2]);
                if (map[i][0] + map[j][0] == 2)
                    gap = Math.min(gap, t);

                dist[i][j] = gap;
                dist[j][i] = gap;
            }
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                if (i == k)
                    continue;

                for (int j = 1; j <= n; j++) {
                    if (j == i || j == k)
                        continue;

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

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

            bw.write(dist[y][x] + "\n");
        }

        bw.flush();
    }

}