[백준] 1238. 파티 / Java

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

1238번: 파티

---

✔ 문제 풀이

조건 분석

• N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
• 각각의 학생들은 파티 장소 X에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다.
• 학생들은 최단 시간에 오고 가기를 원한다.
• 왕복시간이 가장 긴 학생의 소요시간을 구하라.

풀이

학생들은 최단시간에 이동을 원하므로 최단 거리 알고리즘 다익스트라를 생각하였다.

이때, 이동방향에 따라 두 가지로 나누어 볼 수 있다.

1. 집 → 파티 : 각 집에서 파티로 이동하는 최단거리

2. 파티 → 집 : 파티 : 파티에서 각 집으로 이동하는 최단거리

 

2번의 경우 한번의 다익스트라 수행으로 특정 노드(X)에서 다른 모든 노드들로의 최단거리를 구할 수 있다.

하지만 1번의 경우가 이 문제의 재밌는 지점이다. 단순히 생각한다면 시작위치를 각 노드로 잡고 N-1번의 다익스트라를 수행할 수 있는데 이러한 방법은 누가 봐도 비효율적이다.

* 사실 처음에 이렇게 풀었다가 실행시간이 900ms 가 나왔다..

 

이제부터가 소개하는 방식으로 실행시간을 200ms로 줄였다.

 

아이디어는 1번 경우와 2번 경우를 분리시켜 각 경우에서 사용할 간선 정보(list)와 거리 정보(dist)를 따로 생성하는 것이다.

2번 경우(파티→ 집)에는 list, dist.

1번 경우(집→ 파티)에는 reverseList, reverseDist 를 둔다.

 

간선 정보는 출발점(from), 도착점(to), 가중치(weight) 들로 구성되어 있는데

여기서 출발점과 도착점을 서로 바꾸어 그래프(reverseList)에 등록하는 것이다.

이 reverseList를 기반으로 다익스트라를 수행하여 reverseDist에 값을 채워나가면 한번의 다익스트라 수행으로 각 노드에서 X까지의 거리를 한번에 구할 수 있다.

 

추가적인 설명은 코드의 주석으로 이어집니다.

✔ Java Code

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

public class Main {

    static final int INF = 1_000_000_000;
    static int N, M, X;
    static List<List<Node>> list, reverserList;
    static int[] dist, reverseDist;  // 파티에서 각 집으로 가는 거리, 각 집에서 파티로 가는 거리

    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());  // 파티 장소

        list = new ArrayList<>();  // 파티 -> 집
        reverserList = new ArrayList<>();  // 집 -> 파티

        // 리스트 초기화
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
            reverserList.add(new ArrayList<>());
        }

        // 리스트 정보 등록
        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());

            list.get(from).add(new Node(to, weight));
            reverserList.get(to).add(new Node(from, weight));  // 입력값에서의 from과 to를 반전시켜 입력
        }

        System.out.println(solution());
    }

    static int solution() {
        dist = new int[N+1];
        reverseDist = new int[N+1];

        // 거리 배열 초기화
        Arrays.fill(dist, INF);
        Arrays.fill(reverseDist, INF);

        // 시작 위치 X 초기화
        dist[X] = 0;  
        reverseDist[X] = 0;

        // 최단경로 탐색
        dijkstra(list, dist, X);
        dijkstra(reverserList, reverseDist, X);

        // 집에서 파티로 갔다가 다시 집으로 돌아오는 시간의 최댓값을 탐색
        int maxTime = 0;
        for (int i = 1; i <= N; i++) {
            maxTime = Math.max(maxTime, dist[i] + reverseDist[i]);
        }

        return maxTime;
    }
    
    static void dijkstra(List<List<Node>> graph, int[] dist, int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.offer(new Node(start, 0));

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

            // dist배열에 저장되어 있는 현재 노드까지의 거리보다 현재 노드 객체에 담긴 weight 값이 더 크면 다음 노드 탐색으로 건너뛴다
            // 더 진행하여도 dist배열을 갱신할 여지가 없기 때문
            if (dist[curNode.to] < curNode.weight) continue;  

            // 현재 노드의 인접 노드들을 탐색
            for (int i = 0; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                // dist 배열의 원소를 더 작은 값으로 갱신할 수 있는 경우
                if (dist[adjNode.to] > curNode.weight + adjNode.weight) {
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }
        }
    }

    static class Node {
        int to;
        int weight;  // to 노드까지 가는 데 걸리는 시간

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

}