BOJ - 텔레포트3 12908번 (JAVA)

❓ 문제 - 백준 텔레포트3 12908번 - JAVA 풀이법

 

출처 

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

12908번: 텔레포트 3

 

 

 

📝 문제해결법

1. 문제 해석

• 수빈이의 시작 위치(sx, sy)에서 도착 위치(ex, ey)로 이동하기 위한 최소시간을 구해야 합니다.
• 이동하는 방법은 두 가지 방법이 있습니다.
  • 상,하,좌,우로 한 칸씩 이동 (1초)
  • 텔레포트활용하여 이동하며, 텔레포트할 수 있는 방법은 3가지가 있으며 (x1,y1) <-> (x2, y2) 는 서로 이동이 가능(10초)

 

 

2. 이 문제는 플로이드워셜로 해결하였습니다.

• 먼저 위치 좌표의 범위가 10^9이기 때문에 기존에 BFS나 DFS의 방식대로 이동 구현해서 한 칸씩 움직이는 완전탐색 기법하면 시간초과, 메모리초과가 발생합니다.
• 이를 해결하기 위해 시작점, 도착점, 양방향 텔레포트 6가지 지점을 노드로 넣고 각 노드들끼리의 최소 이동거리를 플로이드 워셜 방식으로 구하면 됩니다.
• 플로이드 와샬의 경우 노드 수 (N)이 500개 이하이면 다익스트라와 거의 비슷하게 효율을 낼 수 있기 때문에 해결을 위한 알고리즘으로 선택하였습니다.
• Node 배열에 0인덱스(시작점), 1 ~ 6(각 텔레포트 위치), 7(도착점)으로 셋팅합니다.
• 초반에 시작점 <-> 도착점은 x, y좌표의 차이의 합을 두고, 각 텔레포트간의 최소 이동시간은 x, y좌표의 차이의 합과 10중 최소인 값을 저장합니다.
• 그리고 각 지점마다의 최소 걸리는 거리를 한번 계산 해준 후, 플로이드 워셜로 각 지점 간의 이동 최소시간을 구해줍니다.
• 마지막에 시작점 -> 도착점으로 가는 이동 최소시간인 distance[0][7] 을 답으로 출력합니다.

 

3. 느낀점

• 처음에 10^9 범위에서도 bfs가 돌아가는지 확인하려고 했는데 큐 직전에 방문체크 배열만 선언해줘도 메모리 초과가 났다.
• 여러 방법을 찾아보다가 거의 문제들이  Haming Distance 라는 것을 활용해서 시작점, 도착점, 양방향 텔레포트 6가지 지점의 노드들간의 최소 거리를 구하는 것을 목적으로 풀이가 진행되는 것을 보았기 때문에 이 아이디어를 활용하였다.
• 그리고 생각한대로 구현을 했는데 모든 테케는 맞지만 계속 백준에서 틀렸다고 해서 한 줄 한 줄 코드를 보니... distance 배열에서 int의 범위가 넘는 경우가 저장되서 오버플로우가 생길 수 있는 경우가 있다고 느꼈고 노드들간의 최소 거리를 저장하는 배열 distance를 long 타입으로 변경하니 바로 코드가 통과되었다.
• 히든 테케가 안돌아갈 경우 변수 타입을 꼭 다시 확인하자. 그리고 설계단계부터 타입을 고려해서 설계해야지..!

 

 

💻 소스코드 (JAVA)

// BOJ - 텔레포트(12908)
// 플로이드 워셜


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

public class Main_12908 {
    public static Node[] nodes;
    public static long[][] distance;
    public static int xs, ys, xe, ye;
    public static int INF = Integer.MAX_VALUE;

    public static class Node {
        int x;
        int y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        nodes = new Node[8];
        distance = new long[8][8];

        xs = Integer.parseInt(st.nextToken());
        ys = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        xe = Integer.parseInt(st.nextToken());
        ye = Integer.parseInt(st.nextToken());

        nodes[0] = new Node(xs, ys);
        nodes[7] = new Node(xe, ye);
        for(int i=0;i<8;i++){
            Arrays.fill(distance[i], INF);
        }

        distance[0][7] = distance[7][0] = Math.abs(xs-xe) + Math.abs(ys-ye);
        for(int i=1;i<7;i+=2){
            st = new StringTokenizer(br.readLine(), " ");
            nodes[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            nodes[i+1] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

            distance[i][i+1] = distance[i+1][i] = Math.min(Math.abs(nodes[i].x - nodes[i+1].x) + Math.abs(nodes[i].y - nodes[i+1].y), 10);
        }

        for(int i=0;i<8;i++){
            for(int j=0;j<8;j++){
                distance[i][j] = Math.min(distance[i][j], Math.abs(nodes[i].x-nodes[j].x) + Math.abs(nodes[i].y-nodes[j].y));
            }
        }


        for(int k=0;k<8;k++) {
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }
        }


        System.out.println(distance[0][7]);

    }

}