[java 백준] 골드 3/ 1238번 파티

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

1238번: 파티

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main{
    public static class Node implements Comparable<Node>{
 
        int b;
        int cost;
        public Node(int b,int cost){
            this.b=b;
            this.cost=cost;
        }
 
        //거리가 적은 것 순서대로 우선순위 큐
        @Override
        public int compareTo(Node other){
            return this.cost - other.cost;
        }
 
    }
 
 
 
    public static int n,m,x;
    public static List<Node>[]list;
    public static List<Node>[]reverseList;
    public static int INF=(int)1e9;
    public static int[] dist,reverseDist;
 
 
    //2차원 배열 ArrayList<Node>arr=new ArrayList[n+1]; 하고 반복문으로 안에 arraylist 더 넣어주는 방법도 있고
    //List<List<Node>> list 쓰는 방법도 있음
 
    public static void dijkstra(List<Node>list[],int[]distance,int start){
        PriorityQueue<Node>queue=new PriorityQueue<Node>();
        boolean visit[]=new boolean[n+1];
        queue.add(new Node(start,0));//처음에는 비용이 0임(자기에서 자기로 가니까)
        //distance[i] -->x에서 i로 가는것
        distance[start]=0; //x에서 x가는건 0
 
        while(!queue.isEmpty()){
            int target=queue.poll().b;
            if(!visit[target]){
                visit[target]=true;
 
                for(Node node:list[target]){
                    //node.b도 방문했는지 탐색하는게 중요함.(1번)
                    if(!visit[node.b]&&distance[node.b]>node.cost+distance[target]){
                        distance[node.b]=node.cost+distance[target];
                        queue.add(new Node(node.b,distance[node.b]));
                        //cost자리에 distance[node.b]넣어줘야하는게 핵심! 누적합이 들어가야함.! (2번)
                    }
                }
            }
 
        }
 
 
 
 
    }
 
 
 
    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st=new StringTokenizer(br.readLine());
 
        n=Integer.parseInt(st.nextToken());
        m=Integer.parseInt(st.nextToken());
        x=Integer.parseInt(st.nextToken());
 
        //기준을 x로 잡아야!
        // 모든정점에서 x 까지 (파티 참석) + x에서 모든 정점 (파티 끝나고 집)
 
 
        //특정 정점에서 다른 모든 정점으로 가는 최단거리가 다익스트라
        //모든 정점에서 x까지는 반대로 x에서 모든정점까지인 다익스트라로 구하기 가능(단방향그래프를 반대로)
 
        list =new ArrayList[n+1];
        reverseList=new ArrayList[n+1];
 
        for(int i=0;i<=n;i++){
            list[i]=new ArrayList<Node>();
            reverseList[i]=new ArrayList<Node>();
        }
 
        dist=new int[n+1];
        reverseDist=new int[n+1];
        Arrays.fill(dist,INF);
        Arrays.fill(reverseDist,INF);
 
        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 cost=Integer.parseInt(st.nextToken());
            list[a].add(new Node(b,cost));
            reverseList[b].add(new Node(a,cost));
 
        }
 
        dijkstra(reverseList,reverseDist,x);//모든 정점에서 x로
        dijkstra(list,dist,x);//x에서 모든 정점으로
 
        int max=0;
        for(int i=1;i<=n;i++){
            if(max<reverseDist[i]+dist[i]){
                max=reverseDist[i]+dist[i];
            }
        }
 
        System.out.println(max);
 
 
 
 
 
 
 
    }
}

 

다익스트라를 어떻게 적용할까? 

이 문제는 다익스트라를 활용해서 풀면된다. 문제가 복잡해지거나 어려워질때면 그 문제에 적용되는 개념을 다시 상기시킬 필요가 있다. 다익스트라의 정의는 특정정점에서 모든정점까지 가는 최단거리를 구하는 알고리즘이다.

 

파티장소에서 집에 돌아올때는 특정정점 x에서 모든 정점으로 가지만

집에서 파티장소를 갈때면 모든정점에서 특정정점 x로 가는 것을 생각해줘야 한다. 

이렇게 되면 x를 제외한 모든 노드에 대해서 다익스트라를 적용해야한다. 예를 들면 1번에서 2번으로 가는,3번에서 2번으로 가는,4번에서 2번으로 가는 경우의 수를 모두 다 생각해줘야 한다. 보기만 해도 복잡하고 비효율적이다.

그러면 단방향그래프의 방향을 반대로 바꾸면 2번노드에서 특정정점으로 가는 다익스트라를 사용할 수 있을 것이다. 

결론적으로 말하자면 모든정점에서 2번 정점으로 가는 최단거리 == 단방향 그래프를 반대로 바꿔서 2번에서 모든정점으로 가는 최단거리 

 

queue와 priority queue의 차이점

https://coding-factory.tistory.com/603

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

cf) 힙에 대해서도 알아봅시다

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

 

priority queue는 높은 우선순위 요소를 먼저 꺼내서 처리하는 구조로 이루어져 있다. 

그러기 위해서는 큐에 들어가는 원소는 비교가 가능한 기준이 있어야한다.

 

그럴때 만들어주는 기준 메서드가 comparable이다!

comparable과 compare To의 차이점

 

comparable은 자기자신신과 매개변수의 다른 객체와 비교

compare To는 매개변수로 들어온 서로 다른 두 객체를 비교