백준 24888 (노트 조각) - java

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

 

문제

BOJ 월드에 달리기 대회가 열렸다. BOJ 월드는 1부터 N까지 번호가 매겨진 정점과 M개의 양방향 간선으로 이루어져 있다. 잠시 후 열리는 달리기 대회는 1번 정점에서 출발하며, 가장 먼저 N번 정점에 도착해 자신의 BOJ 계정에 로그인한 사람이 우승한다. 여러 명이 동시에 가장 먼저 로그인에 성공한다면 그 여러 명이 전부 우승한 것으로 하자.

참가자 lobo_prix는 기억력이 좋지 않아 비밀번호를 노트에 적어두는데, 사악한 참가자 jhnah917는 lobo_prix를 방해하기 위해 그 노트를 찢고 노트 조각을 여기저기 숨겨버렸다. lobo_prix는 비밀번호를 기억하지 못하므로 모든 노트 조각을 수집해서 N번 정점으로 가야 한다. jhnah917은 N번 정점까지 최단 경로로만 이동한다.

노트 조각을 줍는 시간과 로그인하는 시간은 무시할만하므로 0이라 가정하자. 또한 모든 참가자의 이동 속도는 동일하다. lobo_prix가 우승할 수 있는 경로가 있을까?

 

유형 : 다익스트라 + DP

 

접근 방식

• 문제의 핵심은 주어진 지점(찢어진 노트가 있는)을 모두 방문하고 최단 거리로 N에 갈 수 있냐라는 것이다.
• 우선 평범한 NlogN 다익스트라를 수행한다.
• 여기서 count[] 배열을 두고 각 지점마다 찢어진 노트 조각을 줍고 방문하는 최대 개수를 DP로 갱신한다.

 

코드

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

public class BOJ_24888_노트_조각 {

    static int n,m;
    static ArrayList<Node>[] graph;
    static int[] isIt;
    static int totalCount;

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

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

        graph = new ArrayList[n+1];
        isIt = new int[n+1];

        for(int i = 1 ; i <= n ; i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i = 1 ; i <= m ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[x].add(new Node(y,c));
            graph[y].add(new Node(x,c));
        }

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++) {
            isIt[i] = Integer.parseInt(st.nextToken());
            totalCount += isIt[i];
        }

        go();

        br.close();
    }


    static void go() {
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.c,y.c)
        );

        int[] path = new int[n+1];
        int[] count = new int[n+1];
        long[] dis = new long[n+1];
        for(int i = 2 ; i <= n ; i++) {
            dis[i] = Long.MAX_VALUE;
        }

        pq.add(new Node(1,0));

        count[1] = isIt[1];

        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            if(cur.v == n)
                continue;

            if(dis[cur.v] < cur.c)
                continue;


            for(Node next : graph[cur.v]) {
                if(dis[next.v] > dis[cur.v] + next.c) {
                    dis[next.v] = dis[cur.v] + next.c;
                    pq.add(new Node(next.v,dis[next.v]));

                    if(count[next.v] <= count[cur.v] + isIt[next.v]) {
                        count[next.v] = count[cur.v] + isIt[next.v];
                        path[next.v] = cur.v;
                    }
                }else if(dis[next.v] == dis[cur.v] + next.c) {
                    if(count[next.v] <= count[cur.v] + isIt[next.v]) {
                        count[next.v] = count[cur.v] + isIt[next.v];
                        path[next.v] = cur.v;
                    }
                }
            }
        }

        if(count[n] == totalCount) {
            Stack<Integer> stack = new Stack<>();
            stack.push(n);
            int tmp = n;

            while(true) {
                tmp = path[tmp];

                if(tmp == 0)
                    break;

                stack.push(tmp);
            }

            System.out.println(stack.size());
            StringBuilder sb = new StringBuilder();
            while(!stack.isEmpty()) {
                sb.append(stack.pop()+" ");
            }
            System.out.println(sb);
        }else {
            System.out.println(-1);
        }
    }


    static class Node {
        int v;
        long c;

        Node(int v,long c) {
            this.v = v;
            this.c = c;
        }
    }
}