BOJ - 달빛 여우 16118번 (JAVA)

❓ 문제 - 백준 달빛 여우 16118번 - JAVA 풀이법

 

출처 

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

16118번: 달빛 여우

 

 

📝 문제해결법

1. 문제 해석

• 여러 노드가 간선을 통해 연결되어 있고, 여우와 늑대가 동시에 1번 노드에서 출발했을 때 여우가 먼저 도착할 수 있는 노드의 갯수를 구하여라.
• 조건 : 늑대는 처음 출발할 때는 간선의 속도를 2배 빠르게 움직이고 그 다음은 2배 느리게 움직이는 특징이 있다.

 

2. 변형된 다익스트라를 통해 문제를 해결하였다.

• 여우의 경우 기존 다익스트라 방법으로 시작점을 1번 노드로 잡고 나머지 노드까지의 최단 거리를 다익스트라를 통해 구했다.
• 늑대의 경우 속도를 2로 나누거나 2를 곱하거나 해야하는데 나누기 처리를 간단히 하기 위해서, 기존의 간선의 거리를 2를 모두 곱해서 ArrayList에 넣어줬다.
• 늑대의 경우 처음시작은 빠름 -> 느림 -> 빠름 -> 느림이 반복됨으로 거리 계산을 위해 사용되는 distance[현재 노드가 어떤 상태에서 시작하는지][노드의 인덱스]의 형태로 저장한다. 현재 노드의 속도 상태는 Node 클래스에 run을 통해 0이면(다음 노드로는 빠르게), 1은 (다음 노드로는 느리게)로 상태를 설정한다.
•  늑대의 다익스트라를 실행할 때 현재 노드에서 다음노드로 빠르게 이동하려면 나누기 2해주고 현재노드에서 다음 노드로 느리게 이동하려면 2를 곱해주면서 cost를 구하였다.
• 여우, 늑대 모두 다익스트라를 돌려준 후 각 노드마다 여우가 늑대보다 빨리 도착한 경우를 distance로 비교해서 더 빨리 도착하면 cnt을 1증가 시킨다.

 

3. 느낀점

1) 늑대의 다익스트라에서 cost를 구할 때 전체 2를 나눠주고나 2를 곱해줘서 자꾸 틀렸는데 자세히 보니 간선의 이동의 속도에만 변화가 있으므로 cost를 구할 때 주의해야했다...

 

2) 최대값을 INF값을 (int)1e9를 했는데 자세히 보니 N*M의 최대 범위를 따졌을 때 거리의 최대값을 (int)2e9로 잡았어야 했다...

 

3) 다 옳바르게 로직을 세웠는데 시간초과가 나길래 또 고민을 많이 하였다. 이 때 다른 사람들의 코드를 보면서 로직은 나와 비슷한데 왜 나만 통과가 안될까? 생각했다.

 

• 첫 번째로 주의할 것은 입력 BufferedReader와 InputStreamReader형태로 받아야 한다는 것이다. 하지만 이건 항상 알고리즘 풀 때 사용하는 입력 기법이라서 나에게 도움이 안되었다.
• 두 번째

public static ArrayList<ArrayList<Node>> list; . . . list = new ArrayList<>();         for(int i=0;i<=n;i++){             distance1[i] = INF;             distance2[0][i] = INF;             distance2[1][i] = INF;             list.add(new ArrayList<>());         }

• 이런 식으로 노드 사이의 간선 정보를 입력받을 때 arraylist에 arraylist를 넣어주고 저장하고 접근하는 방식으로 시간이 많이 소모되는 걸 알았다. 따라서 이 부분을 배열 -> arraylist 형태로 변경해줬다.

public static ArrayList<Node>[] list = new ArrayList[40001]; . . . for(int i=0;i<=n;i++){             distance1[i] = INF;             distance2[0][i] = INF;             distance2[1][i] = INF;             list[i] = new ArrayList<>();         }

• 또한 arraylist의 node에 접근할 때 값이 여러번 참조될 때 변수에 값을 넣어주고 변수로 접근하는 것이 list에 get을 여러번 하지 않아도 되기 때문에 시간을 아낄 수 있는 것 같다.

변경 후 for(Node next:list[node.idx]){                 int next_idx = next.idx;                 int next_dis = next.dis;                 int cost = node.dis + next_dis;                 if(cost < distance1[next_idx]){                     distance1[next_idx] = cost;                     pq.add(new Node(next_idx, cost));                 }             } 변경 전 while (!pq.isEmpty()){             Node node = pq.poll();             if(distance1[node.idx] < node.dis) continue;             for(int i=0;i<list.get(node.idx).size();i++){                 int cost = node.dis + list.get(node.idx).get(i).dis;                 if(cost < distance1[list.get(node.idx).get(i).idx]){                     distance1[list.get(node.idx).get(i).idx] = cost;                     pq.add(new Node(list.get(node.idx).get(i).idx, cost));                 }             }         }

 

 

 

💻 소스코드 

// BOJ - 달빛 여우(16118번)
// 다익스트라
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_16118 {
    public static int n, m;
    public static int[] distance1;
    public static int[][] distance2;
    public static int INF = (int)2e9;
    public static class Node implements Comparable<Node>{
        int idx;
        int dis;
        int run;

        public Node(int idx, int dis){
            this.idx = idx;
            this.dis = dis;
        }

        public Node(int idx, int dis, int run){
            this.idx = idx;
            this.dis = dis;
            this.run = run;
        }

        @Override
        public int compareTo(Node o) {
            if(this.dis < o.dis) return -1;
            return 1;
        }
    }

    public static ArrayList<Node>[] list = new ArrayList[40001];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        distance1 = new int[n+1];
        distance2 = new int[2][n+1];


        for(int i=0;i<=n;i++){
            distance1[i] = INF;
            distance2[0][i] = INF;
            distance2[1][i] = INF;
            list[i] = new ArrayList<>();
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list[a].add(new Node(b, c*2));
            list[b].add(new Node(a, c*2));
        }

        dijkstra();
        dijkstra2();


        int cnt = 0;
        for(int i=2;i<=n;i++){
            int min_value = (int)2e9;
            min_value = Math.min(Math.min(min_value, distance2[0][i]), distance2[1][i]);
            if(distance1[i] < min_value) cnt++;
        }

        System.out.println(cnt);
    }

    public static void dijkstra(){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));
        distance1[1] = 0;

        while (!pq.isEmpty()){
            Node node = pq.poll();
            if(distance1[node.idx] < node.dis) continue;

            for(Node next:list[node.idx]){
                int next_idx = next.idx;
                int next_dis = next.dis;
                int cost = node.dis + next_dis;
                if(cost < distance1[next_idx]){
                    distance1[next_idx] = cost;
                    pq.add(new Node(next_idx, cost));
                }
            }

        }

    }

    public static void dijkstra2(){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0, 0));
        distance2[0][1] = 0;

        while (!pq.isEmpty()){
            Node node = pq.poll();
            if(distance2[node.run][node.idx] < node.dis) continue;


            for(Node next:list[node.idx]){
                int next_idx = next.idx;
                int next_dis = next.dis;

                int cost = node.dis + (node.run == 0 ? next_dis/2 : next_dis*2);
                if(cost < distance2[1-node.run][next_idx]){
                    distance2[1-node.run][next_idx] = cost;
                    pq.add(new Node(next_idx, cost, 1-node.run));
                }
            }

        }

    }
}