[BOJ 1238] 파티 (Java)

문제

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

1238번: 파티

 

풀이

간선 정보가 명시적으로 주어지며, 다익스트라 알고리즘으로 풀 수 있는 문제이다. 

 

1. 다음 노드와 다음 노드로 이동 시의 가중치 값을 저장할 Edge 클래스를 구현한다. 

    public static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight){
            this.to = to;
            this.weight = weight;
        }
    }

 

2. 현재 노드와 현재까지의 가중치합 값을 가지는 Info 클래스를 구현한다. 

    public static class Info implements Comparable<Info> {
        int node;
        int weight;

        public Info(int node, int weight){
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(Info o){
            return this.weight - o.weight;
        }
    }

 

3. Input을 처리하고 답을 출력한다.

현재 노드의 인접 노드들을 저장한다.

N명의 학생 중 X 를 왕복하는데 가장 오래 걸린 학생을 찾아야 하므로,

모든 마을을 순회하면서 완전 탐색하여 dijkstra를 진행한다. 

시작점 -> 목적지 + 목적지 -> 시작점 에 대한 다익스트라 알고리즘을 각각 수행하여 더해준다.

해당 값의 최대 값이 답이 된다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // Node의 개수
        int M = Integer.parseInt(st.nextToken()); // Edge의 개수 (단방향)
        int X = Integer.parseInt(st.nextToken()); // Destination Node

        // 인접 노드 리스트 생성
        ArrayList<Edge> adjs[] = new ArrayList[N+1];
        for(int i = 1; i <= N; i++){
            adjs[i] = new ArrayList<Edge>();
        }
        // 인접 노드 정보 저장
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            adjs[from].add(new Edge(to, weight));
        }

        int max = Integer.MIN_VALUE;
        // 오고 가는데 가장 오래 걸리는 노드의 왕복 시간을 출력
        for(int i = 1; i <= N; i++){
            // 오고가는데 걸리는 시간이므로 시작점 -> 목적지 / 목적지 -> 시작점 값을 더해줘야 함.
            max = Math.max(max, dijkstra(i, X, N, adjs) + dijkstra(X, i, N, adjs));
        }

        System.out.println(max);

 

4. dijkstra 코드는 아래와 같다.

최소 가중치를 저장할 배열을 생성하여 초기값을 INF로 넣어준다.

시작 노드에 대한 정보를 넣어서 탐색을 시작한다.

현재까지의 가중치합 + 인접 노드의 가중치  < 인접 노드의 최소 가중치 배열에 저장된 값  

위 조건을 만족한다면 가중치 배열의 값을 갱신 시켜준 후, 인접 노드의 대한 탐색을 계속 진행한다. 

 

탐색이 끝난 후, dist[X] 에 저장된 값이 S -> X 로 가는 최소 가중치 값이 된다.

    public static int dijkstra(int S, int X, int N, ArrayList<Edge>[] adjs){
        // S 시작점, X 목적지, N 노드개수
        // 최소 가중치 갱신하면서 저장할 배열 생성
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        PriorityQueue<Info> pq = new PriorityQueue<Info>();
        pq.offer(new Info(S, 0));
        dist[S] = 0;

        while(!pq.isEmpty()){
            Info info = pq.poll();
            if(dist[info.node] < info.weight) continue;
            for(Edge edge : adjs[info.node]){
                // 현재 노드의 인접 노드 탐색
                if(info.weight + edge.weight < dist[edge.to]){
                    dist[edge.to] = info.weight + edge.weight;
                    pq.offer(new Info(edge.to, dist[edge.to]));
                }
            }
        }

        return dist[X];
    }

 

소스코드

package dijkstra;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ1238 {

    public static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight){
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Info implements Comparable<Info> {
        int node;
        int weight;

        public Info(int node, int weight){
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(Info o){
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // Node의 개수
        int M = Integer.parseInt(st.nextToken()); // Edge의 개수 (단방향)
        int X = Integer.parseInt(st.nextToken()); // Destination Node

        // 인접 노드 리스트 생성
        ArrayList<Edge> adjs[] = new ArrayList[N+1];
        for(int i = 1; i <= N; i++){
            adjs[i] = new ArrayList<Edge>();
        }
        // 인접 노드 정보 저장
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            adjs[from].add(new Edge(to, weight));
        }

        int max = Integer.MIN_VALUE;
        // 오고 가는데 가장 오래 걸리는 노드의 왕복 시간을 출력
        for(int i = 1; i <= N; i++){
            // 오고가는데 걸리는 시간이므로 시작점 -> 목적지 / 목적지 -> 시작점 값을 더해줘야 함.
            max = Math.max(max, dijkstra(i, X, N, adjs) + dijkstra(X, i, N, adjs));
        }

        System.out.println(max);
    }

    public static int dijkstra(int S, int X, int N, ArrayList<Edge>[] adjs){
        // S 시작점, X 목적지, N 노드개수
        // 최소 가중치 갱신하면서 저장할 배열 생성
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        PriorityQueue<Info> pq = new PriorityQueue<Info>();
        pq.offer(new Info(S, 0));
        dist[S] = 0;

        while(!pq.isEmpty()){
            Info info = pq.poll();
            if(dist[info.node] < info.weight) continue;
            for(Edge edge : adjs[info.node]){
                // 현재 노드의 인접 노드 탐색
                if(info.weight + edge.weight < dist[edge.to]){
                    dist[edge.to] = info.weight + edge.weight;
                    pq.offer(new Info(edge.to, dist[edge.to]));
                }
            }
        }

        return dist[X];
    }
}