[BOJ] 20007.떡 돌리기(그래프).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

문제를 제대로 안 읽어서 헛고생을 엄청나게 했다... 후아

문제가 짧을수록 더 꼼꼼히 읽어보자..!

그냥 문제 좀 제대로 읽자!!

"떡은 한 번에 하나씩만 들고 갈 수 있다" 이걸 못 보고..

정리를 해보자..

* 떡은 한 번에 하나씩만 들고 갈 수 있다

* 집들 사이에는 총 M개의 양방향 도로

* 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문

* 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐

이제 동작을 생각해보자.

1. 다익스트라 알고리즘을 적용하여 성현이의 집부터 이웃 집까지의 최단거리(왕복)를 구하자.

2. 가장 가까운 집부터 방문하기 위해 구한 최단거리 정보를 정렬하자.

3. 최단거리(왕복)가 X보다 큰 집이 있다면 모두 방문할 수 없으므로 -1

4. 가까운 집부터 방문해보자.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class BOJ20007 {
 
    static int N, M, X, Y, INF = Integer.MAX_VALUE;
    static int totalDist[];
    static ArrayList<Edge>[] adj;
    static class Edge implements Comparable<Edge> {
        int to, dist;
        
        public Edge(int to, int dist) {
            super();
            this.to = to;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.dist, o.dist);
        }
        
    }
    
    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()); // 도로 개수
        X = Integer.parseInt(st.nextToken()); // 최대 갈 수 있는 거리
        Y = Integer.parseInt(st.nextToken()); // 성현이 집
        
        totalDist = new int[N];        
        adj = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adj[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 w = Integer.parseInt(st.nextToken());
            // 양방향 도로
            adj[a].add(new Edge(b, w));
            adj[b].add(new Edge(a, w));
        }
        
        System.out.println(process());
    }
 
    private static int process() {
        
        // 성현이 집으로부터 각 집까지의 최단 거리
        dijkstra();
                
        Arrays.sort(totalDist);
        // 최단 거리가 X보다 클 경우(방문할 수 없는 집)
        if(totalDist[N - 1] * 2 > X) return -1;
        
        // 가까운 집부터 방문
        int day = 0, idx = 0, tmp = 0;
        while(idx < N) {
            
            // X 안으로 갈 수 있을 때까지 가보자!
            while(idx < N && tmp + totalDist[idx] * 2 <= X) {
                tmp += totalDist[idx++] * 2;
            }
            
            tmp = 0;
            day++;
        }
                
        return day;
    }
 
    private static void dijkstra() {
        
        Arrays.fill(totalDist, INF);
        
        boolean[] visited = new boolean[N];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        // 성현이 집에서부터 출발
        totalDist[Y] = 0;
        pq.add(new Edge(Y, 0));
        
        while(!pq.isEmpty()) {
            
            Edge now = pq.poll();
            // 이미 방문한 집이면 pass
            if(visited[now.to]) continue;
        
            for (Edge next : adj[now.to]) {
                // 방문하지 않은 집이고, 더 짧은 길로 갈 수 있다면
                if(!visited[next.to] && totalDist[next.to] > totalDist[now.to] + next.dist) {
                    totalDist[next.to] = totalDist[now.to] + next.dist;
                    pq.add(new Edge(next.to, totalDist[next.to]));
                }
            }
            
            visited[now.to] = true;
        }
        
    }
 
}