[JAVA] 백준 20160번 : 야쿠르트 아줌마 야쿠르트 주세요

[문제]

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

20160번: 야쿠르트 아줌마 야쿠르트 주세요

야쿠르트를 외치며 잠에서 깼다. 오늘은 야쿠르트로 하루를 시작하려고 한다.

야쿠르트 아줌마는 10개의 지점을 최단 시간으로 이동하며 들리신다. 각 지점에서 야쿠르트 아줌마보다 같거나 더 일찍 도착한 사람에게 야쿠르트를 팔고 바로 다음 지점으로 출발하신다. 각 지점은 정점 위에 있고 지정된 차례에만 야쿠르트를 판매한다. 야쿠르트를 파는 데 지연되는 시간은 없으며, 오직 이동 시에만 해당 도로의 가중치만큼 시간이 지연된다.

야쿠르트 아줌마는 10개의 지점을 순서대로 방문하며, 10개의 지점 중 첫 번째 지점에서 출발한다. 만약 i번째 지점에서 i+1번째 지점으로 이동 가능한 경로가 없다면 i+2지점으로 이동하신다. i+2로 갈 수 없으면 i+3, i+4...(≤ V)로 이동하신다.

내가 출발하는 시간과 야쿠르트 아줌마가 출발하는 시간은 같다.

내가 출발하는 정점 번호와 야쿠르트 아줌마의 동선을 알려주면 어느 지점으로 가야 야쿠르트를 살 수 있을지 알려줘!!

[입력]

첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다.

그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ u, v ≤ V) 사이에 가중치가 w(1 ≤ w ≤ 100,000)인 도로가 존재한다는 뜻이다. 정점 사이에는 여러 개의 간선이 존재할 수도 있음에 유의한다.

E+2번째 줄에는 야쿠르트 아줌마가 야쿠르트를 파는 10개 지점의 정점 번호가 주어진다. E+3번째 줄에는 내가 출발하는 정점 번호가 주어진다.

[출력]

야쿠르트를 살 수 있는 정점이 여러 개라면 그 중 가장 작은 정점 번호를 출력한다.

야쿠르트를 살 수 없다면 -1을 출력한다.

[예제 입력]

[풀이 과정]

제목이 마음에 들어서 푼 문제였다. 야쿠르트라고 하니까 먹고 싶어졌다.

 

문제를 보면 야쿠르트 아줌마는 10개의 지점을 최단 시간으로 이동하며 들리신다. 정점과 간선 가중치가 입력 값으로 주어지기때문에 그래프 문제라고 생각하였다. 본인은 데이크스트라 알고리즘을 적용시켰다.

 

데이크스트라 (Dijkstra) 알고리즘을 구현하는데 인접 행렬 , 우선순위 큐 방식 이렇게 두 가지 방식이있다. 정점의 수를 V라고 하였을때 인접행렬의 경우 O(V^2) 의 시간복잡도를 갖고 , 우선순위 큐의 경우 O(ElogV)의 시간복잡도를 갖는다. 문제에서 시간 조건이 1초기 때문에 O(V^2)의 풀이는 시간초과가 발생할 것이다. 따라서 우선순위 큐를 이용하여 문제를 풀었다.

 

야쿠르트를 사기 위해서는 아줌마가 지점에 방문한 시간보다 같거나 적어야한다. 또 여러 지점을 갈 수 있으면 작은 번호의 지점을 출력해야한다. 따라서 아줌마가 10개의 지점을 순차적으로 방문할때 걸리는 비용을 구해야 하고 , 본인이 본인의 출발지점에서 다른 지점까지의 최소 비용을 구해야한다.

 

[먼저 본인의 출발 지점에서 다른 지점까지의 최소 비용을 구해보자.]

본인의 출발점 (한 정점 ) 에서 다른 지점까지 (다른 정점)까지의 최단 거리를 구해야하니 데이크스트라 알고리즘을 적용시킨다.

 

[야쿠르트 아줌마가 10개의 지점을 순차적으로 방문할때 최소 비용을 구해보자.]

 

문제 조건중에 i번째 지점을 방문할 수 없으면 i+1 지점을 , 안되면 i+2,i+3 이렇게 i가 증가한다. 따라서 한 지점을 방문했을때 그 지점에서

옆의 지점(오른쪽)을 방문가능 한지 불가능 한지 알아야된다.

 

(1)  i 번째 지점에 방문했다. 데이크스트라 알고리즘을 적용시켜 i 번째 지점으로 부터 다른 지점들까지 가는 최소 비용을 구한다.

 

(2) 이때 다음으로 방문할 수 있는 지점을 찾는다.  (1)에서 구한  i 번째로 부터 구한 최소 비용 배열에서 다음으로 방문 할 수 있는 지점의 인덱스 번호를 구한다.

 

(3) 다음으로 이동할지점까지의 최소 비용과 본인이 이동할 수 있는 최소비용과 비교한다. 야쿠르트를 사려면 본인의 비용이 작거나 같아야한다. 그리고 구매할 수 있다면 그 지점의 번호를 정답 변수에 저장한다. 미리 정답 변수를 MAX(10,001) 값으로 잡고 , 야쿠르트를 구매할 수 있으며 이전에 저장한 지점 번호보다 작은 경우만 정답을 갱신하면된다.

 

(4) 순차적으로 지점을 방문했던 시간을 누적해야 하니 이전까지의 걸린 시간을 저장할 변수(beforetime)를 만들어 지점을 방문할때 매번 갱신해준다. 

 

** 여기서 주의 **

 

어느 한 지점에서 다른 지점으로의 최소 비용을 구할때 데이크스트라를 적용했다. 여기서 나올 수 있는 비용의 최대값은 문제 조건에 따라

10,000 (최대 정점 개수)  *  100,000 (가중치 최대값) = 10억이다. 여기선 int형의 범위를 넘어서지 않는다.  그런데! 야쿠르트 아줌마가 

 

1->2->1->2->1 로 지점을 방문한다고 해보자.

그리고 1->2로 가는 최소 비용이 최악으로 10억이고 2->1로 가는 비용도 10억이였다고 해보자.

 

야쿠르트 아줌마는 지점을 방문할때마다 시간이

1->2 : 10억 

2->1 : (이전 10억) + 10억 

1->2 : (이전:20억) +10억 

2->1 : (이전 30억) +10억

 

 그렇다 이전 방문했던 시간까지 같이 누적해서 구해주어야하기때문에 int형 범위를 (약 -21억 ~+21억) 넘어서게 된다. 따라서 long으로 선언하여 값을 누적하여 더해주어야한다... 아마 이 부분에서 많이 틀리지 않을까 싶다.

 

[코드]

package Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main20160 {
    static class Node {
        int idx;
        int cost;

        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
    static int V , E ;
    public static void main(String[] args)  throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); //정점의 개수
        E = Integer.parseInt(st.nextToken()); //간선의 개수

        //인접 리스트
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();

        for(int i = 0 ; i <=V;i++){
            graph.add(new ArrayList<Node>());
        }

        for(int i = 0 ; i < E; i++){

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

            int from  = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());


            //양방향임에 주의
            graph.get(from).add(new Node(to,cost));
            graph.get(to).add(new Node(from,cost));

        }
        //야구르트 아줌마가 지점 이동하는 순서를 저장한 배열
       int [] moveOrder= new int[10];

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

        for(int i = 0 ; i < 10 ;i++){
            moveOrder[i] = Integer.parseInt(st.nextToken());
        }

        //나의 출발지점
        int myStart = Integer.parseInt(br.readLine());

        //내 출발점으로 부터 다른 지점 까지 가는데 걸리는 비용을 구함
        int [] myCost = dijkstra(graph,myStart);


        //야구르트 아줌마가 이전에 순차적으로 지점을 방문해온 시간을 저장하는 변수
        //**주의 ** : beforetime 은 long으로 선언해야한다.
        //그 이유는 예를 들어 a->b까지 가는 경우의 최소 비용이 최악의 경우 10,000 x 100,000 이면 10억이다.
        //그런데 다음 지점으로 가는게 b->a가 또 최악으로 10억이라고 치자
        //그러면 이전에 방문했던 지점의 시간 비용을 누적해서 더해주어야 할때 20억 이상 , 즉 int형 범위를 넘어선다.
        //따라서 long으로 선언.
        long beforetime = 0;

        int answer  =10_001;

        //내 출발점과 아줌마의 출발점이 같다면 이 출발점을 정답으로 초기화 시켜준다.
        if(myStart ==moveOrder[0]) {
            answer = myStart;
        }

        //야구르트 아줌마가 10개의 지점을 순차적으로 이동
        //8까지만 하게 한 이유는 index 가 9일때는 다음 이동할 지점이 없기때문에 다익스트라 알고리즘을 사용할 필요가 없기때문
        for(int i = 0 ; i <9;i++){

            // (1) i 번째 지점에서 다른 지점으로 가는 최소 비용을 구한다.
          int [] cost = dijkstra(graph,moveOrder[i]);

            //다음 이동 가능한 지점의 인덱스 번호를 저장하기 위한 변수
             int nextIdx = i+1;

             //(2) 방문 할 수 없는 지점이라면  그 다음 번호의 지점을 탐색한다. 방문할 수 있는 지점을 찾는다.
            while (cost[moveOrder[nextIdx]]==Integer.MAX_VALUE){
                //갈수 없는 경우이므로 다음 지점의 인덱스로 증가시킨다.
                   nextIdx++;
                    if(nextIdx>=10){
                        break;
                    }
                }

            //끝지점까지 왔다면 더 이상 구할 필요가 없다.
            if(nextIdx>=10)break;
            
            //(3)
            //야구르트 아줌마가 이동한 지점에 본인이 갈 수 있는지 없는지 비용을 비교한다.
            //여러 야구르트 점을 갈 수 있다면 번호가 작은 지점을 출력해야하므로 최소값으로 갱신한다.
            if(myCost[moveOrder[nextIdx]]<= beforetime+cost[moveOrder[nextIdx]] &&  moveOrder[nextIdx] < answer){
                answer=moveOrder[nextIdx];
            }
            
            //(4)
            
            //다음 방문할 지점의 비용을 구하기 위해 지금까지의 비용을 저장해둔다.
            beforetime+=cost[moveOrder[nextIdx]];

            i=nextIdx-1;


        }
        //방문한 지점이 없다면 -1을 리턴한다.
        if(answer==10_001) answer=-1;
        System.out.println(answer);

    }

    private static int[] dijkstra(ArrayList<ArrayList<Node>> graph ,int start){

        PriorityQueue<Node> queue = new PriorityQueue<>(((o1, o2) -> Integer.compare(o1.cost,o2.cost)));
        int []dist = new int[V+1]; //최소 비용을 저장할 배열

        for(int i = 1 ; i <=V;i++){
            dist[i]= Integer.MAX_VALUE;
        }

        //출발 지점의 최소 비용은  0
        dist[start]=0;

        queue.add(new Node(start,0));

        while (!queue.isEmpty()){

            Node  curNode = queue.poll();

            if(dist[curNode.idx] < curNode.cost){
                continue;
            }

            for(int i = 0 ; i < graph.get(curNode.idx).size();i++){

                Node  nxtNode = graph.get(curNode.idx).get(i);

                if(dist[nxtNode.idx] > dist[curNode.idx] + nxtNode.cost){
                    dist[nxtNode.idx] = dist[curNode.idx] + nxtNode.cost;
                    queue.add(new Node(nxtNode.idx,dist[nxtNode.idx]));
                }
            }

        }
        return dist;
    }
}

 

[결과]

야쿠르트가 싫어졌다.