[JAVA] 다익스트라 알고리즘 뿌수기4

 

다익스트라 뿌수기 시즌4다

 

이전글

https://fladi.tistory.com/399

[JAVA] 다익스트라 알고리즘 뿌수기

https://fladi.tistory.com/400

[JAVA] 다익스트라 알고리즘 뿌수기2

https://fladi.tistory.com/403

[JAVA] 다익스트라 알고리즘 뿌수기3

 

 

 

 

9370 미확인 도착지 - 골드2

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

9370번: 미확인 도착지

• 다익스트라인데, 최단경로가 어떤 경로를 꼭 포함해야하는 경우가 포함된 문제다
• 최단경로의 경우의 수가 여러 개 나올 수 있다는 점을 잘 생각해야한다. 

 

class Node implements Comparable<Node> {
    int length;
    int end;

    public Node(int length, int end) {
        this.length = length;
        this.end = end;
    }

    @Override
    public int compareTo(Node o) {
        return length - o.length;
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static TreeSet<Integer> result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc<tcCnt; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int crossWayCnt = Integer.parseInt(st.nextToken());
            int roadCnt = Integer.parseInt(st.nextToken());
            int targetCandidateCnt = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            result = new TreeSet();

            int start = Integer.parseInt(st.nextToken())-1;
            int pass1 = Integer.parseInt(st.nextToken())-1;
            int pass2 = Integer.parseInt(st.nextToken())-1;

            arr = new ArrayList[crossWayCnt];
            for (int i =0; i<arr.length; i++) {
                arr[i] = new ArrayList<>();
            }

            int smallLen = 0;

            for (int i =0; i<roadCnt; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken())-1;
                int b = Integer.parseInt(st.nextToken())-1;
                int len = Integer.parseInt(st.nextToken());

                arr[a].add(new Node(len, b));
                arr[b].add(new Node(len, a));

                if ((a == pass1 && b == pass2) || (a == pass2 && b == pass1)) {
                    smallLen = len;
                }
            }

            int[] candidate = new int[targetCandidateCnt];
            for (int i =0; i<targetCandidateCnt; i++) {
                candidate[i] = Integer.parseInt(br.readLine())-1;
            }

            for (int i =0; i<targetCandidateCnt; i++) {
                int global = dijkstra(start, candidate[i]);
                int local1 = dijkstra(start, pass1) + dijkstra(pass2, candidate[i]) + smallLen;
                int local2 = dijkstra(start, pass2) + dijkstra(pass1, candidate[i]) + smallLen;

                if (local1 == global || local2 == global) {
                    result.add(candidate[i]);
                }
            }

            while(!result.isEmpty()) {
                sb.append((result.pollFirst()+1) + " ");
            }
            sb.append("\n");
        }

        System.out.print(sb);
    }

    private static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(0, start));

        boolean[] visit = new boolean[arr.length];
        int[] prev = new int[arr.length];
        int[] value = new int[arr.length];
        Arrays.fill(value, Integer.MAX_VALUE);
        prev[start] = start;
        value[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (!visit[current]) {
                visit[current] = true;

                if (current == end) {
                    break;
                }

                for (Node adj: arr[current]) {
                    if (!visit[adj.end] && value[adj.end] > value[current] + adj.length) {
                        value[adj.end] = value[current] + adj.length;
                        prev[adj.end] = current;
                        pq.add(new Node(value[adj.end], adj.end));
                    }
                }
            }
        }

        return value[end];
    }
}

• 최단경로에서만 prev값을 구하면 다른 경로도 있을 수 있다
• 그래서 꼭 들러아하는 곳도 다익스트라로 길이를 구해줬다.
  • start -> pass1 -> pass2 -> end
  • start -> pass2 -> pass1 -> end
• 최단 경로와 경유경로의 길이가 같다면 최단경로에 해당 경로가 포함되는 거라 result에 추가해줬다
• result는 오름차순으로 바로 받기 위해 TreeSet을 사용했다

 

 

 

16681 등산 - 골드2

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

16681번: 등산

• 삽질을 많이했다
• 진짜 하 타입..... 타입 제발 생각하기...

 

class Node implements Comparable<Node> {
    int end;
    long value;

    public Node(int end, long value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        if (value > o.value) {
            return 1;
        } else {
            return -1;
        }
    }
}

public class Main {
    static ArrayList<Node>[] upArr;
    static ArrayList<Node>[] downArr;

    static long[] upValue;
    static long[] downValue;
    static int[] height;

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

        int nodeCnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());
        int consumption = Integer.parseInt(st.nextToken()); //거리당 체력소모량
        int accomplishment = Integer.parseInt(st.nextToken()); //높이당 성취감

        height = new int[nodeCnt];
        upValue = new long[nodeCnt];
        downValue = new long[nodeCnt];
        upArr = new ArrayList[nodeCnt];
        downArr = new ArrayList[nodeCnt];
        for (int i = 0; i < upArr.length; i++) {
            upArr[i] = new ArrayList<>();
            downArr[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < nodeCnt; i++) {
            height[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int length = Integer.parseInt(st.nextToken());

            if (height[a] > height[b]) {
                upArr[b].add(new Node(a, length));
                downArr[b].add(new Node(a, length));
            } else if (height[a] < height[b]) {
                downArr[a].add(new Node(b, length));
                upArr[a].add(new Node(b, length));
            }
        }

        upDijkstra(0);
        downDijkstra(nodeCnt - 1);

        long max = Long.MIN_VALUE;
        for (int i = 1; i < nodeCnt - 1; i++) {
            long up = upValue[i];
            if (up == Long.MAX_VALUE) {
                continue;
            }

            long down = downValue[i];
            if (down == Long.MAX_VALUE) {
                continue;
            }

            long tmp = (long) accomplishment * height[i] - up*consumption - down*consumption;
            if (tmp > max) {
                max = tmp;
            }
        }

        if (max == Long.MIN_VALUE) {
            System.out.println("Impossible");
        } else {
            System.out.println(max);
        }
    }

    private static void upDijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        boolean[] visit = new boolean[downArr.length];

        Arrays.fill(upValue, Long.MAX_VALUE);
        upValue[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (!visit[curr]) {
                visit[curr] = true;

                for (Node adj : upArr[curr]) {
                    if (!visit[adj.end] && upValue[adj.end] > upValue[curr] + adj.value) {
                        upValue[adj.end] = upValue[curr] + adj.value;
                        pq.add(new Node(adj.end, upValue[adj.end]));
                    }
                }
            }
        }
    }

    private static void downDijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        boolean[] visit = new boolean[downArr.length];

        Arrays.fill(downValue, Long.MAX_VALUE);
        downValue[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (!visit[curr]) {
                visit[curr] = true;

                for (Node adj : downArr[curr]) {
                    if (!visit[adj.end] && downValue[adj.end] > downValue[curr] + adj.value) {
                        downValue[adj.end] = downValue[curr] + adj.value;
                        pq.add(new Node(adj.end, downValue[adj.end]));
                    }
                }
            }
        }
    }
}

• 올라갈 수 있는 곳과 내려갈 수 있는 곳을 따로 생각한다
• 시작점부터 모든 지점까지 올라갈 수 있는 거리를 upValue에 저장
• 끝점부터 모든 지점까지 올라갈 수 있는 거리를 downValue에 저장(다익스트라로 풀기위해 조금 변형했다)
• 각각 다익스트라 해서 올라가고 내려갈 수 있는 길이 있다면 성취감과 더함 
  • 이 값들 중 가장 큰 값을 구한다
  • 음수가 될 수 있다는 것에 유의한다

 

 

 

17835 면접보는 승범이네 - 골드2

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

17835번: 면접보는 승범이네

• 면접장 -> 모든 집까지의 길이를 구하면 시간이 너무 많이 걸릴 것 같음. 모든 집 -> 가장 가까운 면접장까지 길이를 다익스트라로 구하는 게 좋겠다.
• 그런데 면접장이 굉장히 많은경우 하나하나 비교하는 데 시간이 많이 걸릴 것 같다.
• 플루이드 워샬로 구한다면 구하는 건 빠르겠지만 각 면접장과 거리를 비교해야한다.
• 일반적으로는 다익스트라가 빠를 것 같은데, 면접장이 많다면 플루이드가 빠를듯. 일단 다익스트라로 해봐야겠다

결과는 시간초과..

 

 

어떻게 시간을 줄일지 생각해봤다..

단방향이라서 각 점마다 최단거리는 구해야할거고/ 면접장과 가장 가까워지면 리턴하는 게 좋음

매번 비교하지 않고 마지막에 비교하는 방식으로 구해볼까?

 

획기적인 방법이 필요할 것 같은데 떠오르지 않는다... 구글링 해봄

 

와 진짜 획기적인 방법을 찾아냈다. 소름돋는다. 이 문제를 풀게된게 너무 행운이다. 

힌트는 다익스트라의 시작점이 여러 개 일 수 있다는 것!!!!! 😆😆😆😆😆😆

이런 발상을 알게되서 너무 기쁘다. 이 방법으로 풀어보겠다!

 

하지만 계속되는 틀렸습니다... 중꺾마 하면서 겨우 풀어냈다.

틀린이유는 마지막에 value들을 돌면서 최솟값을 찾기 싫어서 찾는 도중에 확인하려다 계속 틀렸다. 초기에 초기화하는 코드 부분이 잘못됐던 것 같다. (면접장인 곳 중에 최솟값을 찾는 과정 등)

 

class Node implements Comparable<Node> {
    int end;
    long value;

    public Node(int end, long value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        if (value > o.value) {
            return 1;
        } else {
            return -1;
        }
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static long[] value;
    static int countryNum = 0;
    static long max = -1;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int countryCnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());
        int buildingCnt = Integer.parseInt(st.nextToken());

        arr = new ArrayList[countryCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int c = Integer.parseInt(st.nextToken())-1;
            int length = Integer.parseInt(st.nextToken());

            arr[c].add(new Node(a, length));
        }

        value = new long[arr.length];
        Arrays.fill(value, Long.MAX_VALUE);

        st = new StringTokenizer(br.readLine());
        for (int i =0; i<buildingCnt; i++) {
            int b = Integer.parseInt(st.nextToken())-1;
            value[b] = 0;
            pq.add(new Node(b, 0));
        }

        dijkstra();

        System.out.println(countryNum);
        System.out.println(max);
    }

    private static void dijkstra() {
        boolean[] visit = new boolean[arr.length];

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (!visit[current]) {
                visit[current] = true;

                for (Node adj: arr[current]) {
                    if (!visit[adj.end] && value[adj.end] > value[current] + adj.value) {
                        value[adj.end] = value[current] + adj.value;
                        pq.add(new Node(adj.end, value[adj.end]));
                    }
                }
            }
        }

        for (int i =0; i<value.length; i++) {
            if (max < value[i]) {
                max = value[i];
                countryNum = i+1;
            }
        }
    }
}

 

 

 

14554 The Other Way - 골드1

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

14554번: The Other Way

• 아래 문제를 풀다 다익스트라의 다른 경우의 수를 찾아야할 것 같아서 비슷한 다른 문제를 풀어보려고 한다
• (골드1인게 두렵다)

 

class Node implements Comparable<Node> {
    int end;
    long value;

    public Node(int end, long value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return Long.compare(value, o.value);
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static int MOD = 1000000009;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int countryCnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken()); //양방향
        int start = Integer.parseInt(st.nextToken())-1;
        int end = Integer.parseInt(st.nextToken())-1;

        arr = new ArrayList[countryCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(b, distance));
            arr[b].add(new Node(a, distance));
        }

        long caseCnt = dijkstra(start, end);

        System.out.println(caseCnt);
    }

    private static long dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        long[] caseCnt = new long[arr.length];
        boolean[] visit = new boolean[arr.length];
        long[] value = new long[arr.length];

        Arrays.fill(value, Long.MAX_VALUE);
        value[start] = 0;
        caseCnt[start] = 1;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (!visit[current]) {
                visit[current] = true;

                if (current == end) {
                    break;
                }

                for (Node adj: arr[current]) {
                    if (!visit[adj.end]) {
                        if (value[adj.end] > value[current] + adj.value) {
                            value[adj.end] = value[current] + adj.value;
                            caseCnt[adj.end] = caseCnt[current];
                            pq.add(new Node(adj.end, value[adj.end]));
                        } else if (value[adj.end] == value[current] + adj.value) {
                            caseCnt[adj.end] = (caseCnt[adj.end] + caseCnt[current]) % MOD;
                        }
                    }
                }
            }
        }

        return caseCnt[end];
    }
}

• 개념은 아래의 블로그를 참고하였다
  • https://hyeonyeee.tistory.com/82
• 어떤 노드로 가는 최단경로가 2개이상 있으면 이전노드의 경로를 더해주는 방식을 사용하였다
• 그러면 경우의 수가 노드에 계속 저장됨
• 다익스트라니까 항상 최단경로부터 Priority Queue에서 빠진다 -> 종점에 도착하면 break치고 해당 경우의 수를 return하면 된다
• 다익스트라의 새로운 접근이라 재미있다!

 

 

 

 

1162 도로포장 - 플레5

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

1162번: 도로포장

• 나는 겁쟁이라 골드1을 손댈 생각도 못했었다. 하지만 용기를 내서 이번에 도전해봤다. (분명 어제까지 골드1이었는데 플레5로 바뀜)
• 골드2쯤 문제부터 dp를 사용할 수 있다는 걸 봤지만 애써 무시했었다. 하지만 이 문제는 dp가 필수인 듯 하다.
  • k를 하나씩 늘리면서 계산하는 건 dp냄새가 나고
  • 최단거리 찾는 건 다익스트라 냄새가 난다
  • dp + 다익스트라 문제였음 ..
• dp를 사용하면서 visit 배열도 이제 사용하지 못했다. 3차원 배열이라 메모리가 상당히 많이 들 듯

 

class Node implements Comparable<Node> {
    int end;
    int count;
    long value;

    public Node(int end, int count, long value) {
        this.end = end;
        this.count = count;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return Long.compare(value, o.value);
    }
}

public class Main {
    static ArrayList<Node>[] arr;
    static int kCnt;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int countryCnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken()); //양방향
        kCnt = Integer.parseInt(st.nextToken());

        arr = new ArrayList[countryCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(b, 0, distance));
            arr[b].add(new Node(a, 0, distance));
        }

        System.out.println(dijkstra(0, countryCnt-1));
    }

    private static long dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0, 0));

        long[][] value = new long[kCnt+1][arr.length];

        for (int i =0; i<value.length; i++) {
            Arrays.fill(value[i], Long.MAX_VALUE);
            value[i][start] = 0;
        }

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;
            int count = currentNode.count;

            if (currentNode.value > value[count][current]) {
                continue;
            }

            for (Node adj: arr[current]) {
                if (value[count][adj.end] > value[count][current] + adj.value) {
                    value[count][adj.end] = value[count][current] + adj.value;
                    pq.add(new Node(adj.end, count, value[count][adj.end]));
                }

                if (count+1 <= kCnt && value[count+1][adj.end] > value[count][current]) {
                    value[count+1][adj.end] = value[count][current];
                    pq.add(new Node(adj.end, count+1, value[count+1][adj.end]));
                }
            }
        }

        long minTime = Long.MAX_VALUE;
        for (int i=0; i<=kCnt; i++) {
            if (minTime > value[i][end]) {
                minTime= value[i][end];
            }
        }

        return minTime;
    }
}

• 마지막에 k개를 모두 사용하지 않아도 최단시간이 나올 수 있기 때문에 value[i][end] 의 모든 값 중 최솟값을 찾아야한다

 

 

 

 

2307 도로검문 - 골드1

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

2307번: 도로검문

• 도로를 하나 막아야함
• 일단 최단 시간을 구하고
• 도로를 하나씩 막으면서 지연시간을 계산한다
• 최대 5000개를 하나씩 다 막아보면서 구한다기보단, 최단거리에 포함된 거리를 하나씩 막으면서 구해보면 될듯
  
  • 이후 하나씩 막고 다익스트라를 진행하면서 최대 거리를 찾으면 되겠다

 

class Node implements Comparable<Node> {
    int end;
    int value;

    public Node(int end, int value) {
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return value - o.value;
    }
}

public class Main {
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static ArrayList<Node>[] arr;
    static int roadCnt;
    static int[] values;
    static int[] prev;

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

        int pointCnt  = Integer.parseInt(st.nextToken());
        roadCnt =  Integer.parseInt(st.nextToken());

        arr = new ArrayList[pointCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        values = new int[pointCnt];
        prev = new int[pointCnt];

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int time = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(b, time));
            arr[b].add(new Node(a, time));
        }

        int global = dijkstra(0, pointCnt-1);

        if (global == Integer.MAX_VALUE) {
            System.out.println(-1);
            return;
        }

        int max = -1;
        int curr = pointCnt-1;
        while (curr != 0) {
            int p = prev[curr];
            int local = dijkstra2(0, pointCnt-1, curr, p);
            if (local > max) {
                max = local;
            }
            curr = p;
        }

        if (max == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(max - global);
        }
    }

    private static int dijkstra(int start, int end) {
        pq.add(new Node(start, 0));

        Arrays.fill(values, Integer.MAX_VALUE);
        values[start] = 0;
        prev[start] = start;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (values[current] < currentNode.value) {
                continue;
            }

            if (current == end) {
                break;
            }

            for (Node adj: arr[current]) {
                if (values[adj.end] > values[current] + adj.value) {
                    values[adj.end] = values[current] + adj.value;
                    prev[adj.end] = current;
                    pq.add(new Node(adj.end, values[adj.end]));
                }
            }
        }

        pq.clear();

        return values[end];
    }

    private static int dijkstra2(int start, int end, int block1, int block2) {
        pq.add(new Node(start, 0));

        Arrays.fill(values, Integer.MAX_VALUE);
        values[start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int current = currentNode.end;

            if (values[current] < currentNode.value) {
                continue;
            }

            if (current == end) {
                break;
            }

            for (Node adj: arr[current]) {
                if ((current == block1 && adj.end == block2) || (current == block2 && adj.end == block1)) {
                    continue;
                }

                if (values[adj.end] > values[current] + adj.value) {
                    values[adj.end] = values[current] + adj.value;
                    pq.add(new Node(adj.end, values[adj.end]));
                }
            }
        }

        pq.clear();

        return values[end];
    }
}

 

• 다익스트라를 하면서 dp처럼 저장하고 싶었는데, 최댓값을 구하는 거라 마땅한 생각이 떠오르지 않았다
• 어차피 하나만 막는거니 최단경로 내의 간선만 포함하지 않게 다익스트라를 돌려줬다
• 시간을 줄이기 위해 end값에 도달하면 break를 해줬는데, PriorityQueue를 static으로 선언했기 때문에 마지막에 clear과정이 필수다

 

 

 

 

16118 달빛 여우 - 골드1

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

16118번: 달빛 여우

• 어느덧 마지막 부수기 문제다.. (아직도 부족한 것 같아 다음에 2차 부수기도 해야겠다)
• 다익스트라를 돌리되, 달빛늑대는 짝수번째 홀수번째를 구별하여 value를 관리하면 될 것 같다.
• 그루터기의 개수를 구해야하므로 목적지 전체에 대해 다익스트라 해야할듯
• +) 참고로 늑대는 시작점에 다시 돌아와야 더 빠른 경우가 존재함
  • 블로그 참고: https://maivve.tistory.com/238

 

class Node implements Comparable<Node> {
    int end;
    long value;
    boolean isRun;

    public Node(int end, long value, boolean isRun) {
        this.end = end;
        this.value = value;
        this.isRun = isRun;
    }

    @Override
    public int compareTo(Node o) {
        return Long.compare(value, o.value);
    }
}

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

        int treeCnt = Integer.parseInt(st.nextToken());
        int roadCnt = Integer.parseInt(st.nextToken());

        arr = new ArrayList[treeCnt];
        for (int i =0; i<arr.length; i++) {
            arr[i] = new ArrayList<>();
        }

        for (int i =0; i<roadCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken())-1;
            int b = Integer.parseInt(st.nextToken())-1;
            int distance = Integer.parseInt(st.nextToken());

            arr[a].add(new Node(b, distance*2, false));
            arr[b].add(new Node(a, distance*2, false));
        }

        int result = 0;
        long[] fox = dijkstra(0, true);
        long[] wolf = dijkstra(0, false);
        for (int i =1; i<fox.length; i++) {
            if (fox[i] < wolf[i]) {
                result++;
            }
        }

        System.out.println(result);
    }

    private static long[] dijkstra(int start, boolean isFox) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0, false));

        long[][] values = new long[2][arr.length]; //0 -> 달려서 도착, 1 -> 안달려서 도착
        Arrays.fill(values[0], Long.MAX_VALUE);
        Arrays.fill(values[1], Long.MAX_VALUE);
        values[1][start] = 0;

        while (!pq.isEmpty()) {
            Node currentNode = pq.poll();
            int curr = currentNode.end;

            if (isFox) {
                if (values[0][curr] < currentNode.value) {
                    continue;
                }

                for (Node adj: arr[curr]) {
                    if (values[0][adj.end] > currentNode.value + adj.value) {
                        values[0][adj.end] = currentNode.value + adj.value;
                        pq.add(new Node(adj.end, values[0][adj.end], false));
                    }
                }
            } else {
                if (currentNode.isRun) { //안뛰어서 도착
                    if (values[0][curr] < currentNode.value) {
                        continue;
                    }

                    for (Node adj: arr[curr]) {
                        if (values[1][adj.end] > currentNode.value + adj.value*2) {
                            values[1][adj.end] = currentNode.value + adj.value*2;
                            pq.add(new Node(adj.end, values[1][adj.end], false));
                        }
                    }
                } else { //뛰어서 도착
                    if (values[1][curr] < currentNode.value) {
                        continue;
                    }

                    for (Node adj: arr[curr]) {
                        if (values[0][adj.end] > currentNode.value + adj.value/2) {
                            values[0][adj.end] = currentNode.value + adj.value/2;
                            pq.add(new Node(adj.end, values[0][adj.end], true));
                        }
                    }
                }
            }
        }

        if (isFox) {
            return values[0];
        } else {
            for (int i =1; i<values[0].length; i++) {
                values[0][i] = Math.min(values[0][i], values[1][i]);
            }
            return values[0];
        }
    }
}

• 나누기 2 연산이 있기 때문에 double을 쓰는 것 보단 long을 쓰되 전체 거리에 2를 곱하는 게 효율적이다
• 늑대의 경우 그루터기마다 뛰어서 도착할 때와 안뛰어서 도착할 때를 구분하여 value를 저장한다
• 뛰어서 도착, 안뛰어서 도착 2개를 비교하여 작은 값을 반환한다
• 여우는 그냥 다익스트라임

 

 

 

 

 

 

 

 

하 다뿌쉈다..

아직도 부족한 것 같아 2회독은 해야할 것 같다.