[백준] 12908번 텔레포트 3

문제 설명

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

문제 풀이

• 다익스트라 알고리즘을 이용하여 풀이하였다.
• 텔레포트 노드 간의 거리를 구할때 점프와 텔레포트중 작은 값을 취해야 한다.
• 다익스트라 거리 계산 시 중간값이 int 범위를 넘을 수 있어 long으로 지정해주었다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static Point[] node = new Point[9];
    public static long[][] adj = new long[9][9];

    public static class Point implements Comparable<Point>{
        long x, y;

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

        @Override
        public int compareTo(Point o) {
            if (this.y > o.y) return 1;
            else return -1;
        }
    }

    public static long dijkstra() {
        PriorityQueue<Point> q = new PriorityQueue<>();
        long[] dist = new long[9];
        Arrays.fill(dist, Long.MAX_VALUE);
        q.add(new Point(1, 0));
        while(!q.isEmpty()) {
            Point cur = q.poll();
            if (cur.y > dist[(int)cur.x]) continue;
            for (int i = 1; i <= 8; i++) {
                long nextDist = cur.y + adj[(int)cur.x][i];
                if (nextDist < dist[i]) {
                    dist[i] = nextDist;
                    q.add(new Point(i, nextDist));
                }
            }
        }
        return dist[2];
    }

    public static void input() throws IOException {
        for (int i = 0; i < 9; i++) node[i] = new Point(0, 0);
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        node[1].x = Integer.parseInt(st.nextToken());
        node[1].y = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        node[2].x = Integer.parseInt(st.nextToken());
        node[2].y = Integer.parseInt(st.nextToken());
        int cur = 3;
        for (int i = 0; i < 3; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            node[cur].x = Integer.parseInt(st.nextToken());
            node[cur++].y = Integer.parseInt(st.nextToken());
            node[cur].x = Integer.parseInt(st.nextToken());
            node[cur++].y = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i <= 8; i++) {
            for (int j = 1; j <= 8; j++) {
                if (i == j) continue;
                long dist = Math.abs(node[i].x - node[j].x) + Math.abs(node[i].y - node[j].y);
                if (((i == 3 && j == 4) || (i == 4 && j == 3)) && dist > 10) adj[i][j] = 10;
                else if (((i == 5 && j == 6) || (i == 6 && j == 5)) && dist > 10) adj[i][j] = 10;
                else if (((i == 7 && j == 8) || (i == 8 && j == 7)) && dist > 10) adj[i][j] = 10;
                else adj[i][j] = dist;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(dijkstra() + "\n");
        bw.flush();
        bw.close();
        bw.close();
    }
}