[백준] 1238번 파티 (Java)

1238번 파티 문제 풀러 가기

1238번: 파티

 

 

1. 문제 분석

---

• N명의 학생들은 X번 마을까지 갔다가 다시 돌아와야 한다.
• 이때 갔다가 다시 돌아오는 최단 거리를 구해야 한다.
• 각 마을에서 마을로 이동하는 데는 양의 가중치(거리)가 존재한다.

 

 

 

2. 생각해 보기

---

• 양의 가중치가 존재하기 때문에 다익스트라 아니면 플로이드 와샬을 고려해 본다.
• 플로이드 와샬 알고리즘은 O(N^3)의 시간 복잡도가 필요하다. 마을의 개수(N)가 최대 10^3이기 때문에 플로이드 와샬을 사용하면 최대 10^9의 시간이 걸릴 수 있어 시간 초과가 날 가능성이 있다.
• 그럼 고려해 볼 수 있는 알고리즘은 다익스트라 알고리즘이다.
• 다음은 각 마을에서 X로 가는 최단 거리와, X에서 다시 각 마을로 돌아가는 최단 거리를 구해야 한다.
• 그대로 구현한다면 1, 3, 4 마을에서 각각 2번 마을까지 갈 수 있는 거리를 구해야 한다. 이를 반대로 생각해 보면 다음과 같이 접근해 볼 수 있다.
   
  1. (시작 마을) (끝 마을) (거리)를 입력받을 때, 입력받은 대로 저장하는 경우 map과 (끝 마을) (시작 마을) (거리)로 저장하는 경우reverseMap을 모두 저장한다.
  2. X 마을에서 각 마을(1, 3, 4)로 돌아가는 경우를 구할 때는 map을 사용하면 X 마을을 시작점으로 각 마을로 돌아가는 거리를 구할 수 있다.
  3. 각 마을(1, 3, 4)에서 X 마을로 가는 경우를 구할 때는 reverseMap을 사용하면 X 마을을 시작점으로 각 마을로 가는 거리를 구할 수 있다.
  4. 이렇게 reverseMap을 사용하면 X 마을이 도착점이 아닌 시작 마을로 해서 간단하게 다익스트라 알고리즘을 2번 돌려주면 원하는 값을 얻을 수 있다.

 

 

 

3. 소스코드

---

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, X;
    static List<Node>[] map, reverseMap; // 인접 리스트로 저장

    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());
        map = new ArrayList[N + 1];
        reverseMap = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            map[i] = new ArrayList<>();
            reverseMap[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int dist = Integer.parseInt(st.nextToken());
            map[start].add(new Node(end, dist));
            reverseMap[end].add(new Node(start, dist));
        }
        int[] go = dijkstra(reverseMap); // 각 노드에서 X로 가는 최단 경로
        int[] back = dijkstra(map); // X에서 각 노드로 가는 최단 경로

        int answer = 0;
        for (int i = 1; i <= N; i++) {
            answer = Math.max(answer, go[i] + back[i]);
        }
        System.out.println(answer);
    }

    public static int[] dijkstra(List<Node>[] inputMap) {
        boolean[] visited = new boolean[N + 1];
        int[] result = new int[N + 1];
        Arrays.fill(result, Integer.MAX_VALUE);
        result[X] = 0; // X에서 X로 가는 경로는 0으로 초기화

        // 다익스트라 알고리즘 시작
        PriorityQueue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.dist - n2.dist);
        queue.add(new Node(X, 0));

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            if (visited[curr.end]) {
                continue;
            }
            visited[curr.end] = true;
            for (Node node : inputMap[curr.end]) {
                if (curr.dist + node.dist < result[node.end]) {
                    result[node.end] = curr.dist + node.dist;
                }
                queue.add(new Node(node.end, result[node.end]));
            }
        }
        return result;
    }

    static class Node {
        int end, dist;

        public Node (int end, int dist) {
            this.end = end;
            this.dist = dist;
        }
    }
}

• 저는 다익스트라 알고리즘에 사용될 map과 reverseMap을 인접리스트 형식으로 저장했습니다.
• PriorityQueue를 사용해서 Node의 dist(거리)를 기준으로 오름차순 정렬되도록 선언했습니다.
• 거리 기준 오름차순으로 저장하면 해당 노드로 도달할 수 있는 최단 거리를 얻을 수 있고, 같은 노드에 대한 정보가 나중에 들어오면 visited를 통해서 contitnue로 걸러줬습니다.

 

 

 

4. 알게 된 점

---

• 그래프에서 어떤 특정 노드까지 이동을 하고, 다시 되돌아와야 하는 경우가 존재한다면, 해당 특정 노드를 시작점으로 해결해 볼 수 있다는 것을 알게 되었습니다. (입력을 거꾸로 저장, reverseMap)