백준 - 1238 파티

---

풀이 방법

다익스트라 알고리즘을 공부했기에...도전했던 문제ㅠㅠ

근데 '공부한 것' 과 공부한 것을 문제에 적용하는 것은 다르더라는 것을 깨달았다. 수학 공부하면서 공식을 아는 것과 적용하는게 다시 한번 느꼈달까ㅠㅠ

 

이 문제의 포인트는 각 마을에서 X 를 방문했다가 다시 X에서 각 마을로 돌아오는 것! 을 모두 계산해야한다는 점이다.

 

단순히 가는 것만 계산해서도 안되고, 집으로 오는 것만 계산해서도 안된다. 때문에 이 문제는 다익스트라 알고리즘을 총 2번 사용해서 답을 구하게 된다.

정확히는 X 에서 각 마을로 가는 최소 방문 비용을 구한 후 bakHome 에 저장하고, 각 마을에서 X 로 가는 최소 방문 비용을 구해서 goX 에 저장한다.

 

이때 X -> 각 마을 까지는 다익스트라를 이용하면 되는데, 각 마을에서 X 로 가는게 가장 큰 문제가 된다. 이때 플로이드 와샬 알고리즘(...) 을 사용하면 된다는데 나는 그런거 모르니까 다른 방법으로 생각을 해보았다.

 

바로 그래프를 가는 것과 오는 것 모두 저장하는 것이다.

뭔말이냐 하면 처음 입력받는 값들에 대해서 n -> m 과 그 비용만 배열에 저장하는 것이 아닌 입력받는 간선의 값을 전부 뒤집어서 m -> n 과 그 비용을 모두 저장하는 것이다.

# n, m, cost 를 아래처럼 입력받을 때
1 2 4
1 3 2
3 1 2
2 1 1

# n, m, cost 정상 그래프
1 -> 2 : 비용 4
1 -> 3 : 비용 2
3 -> 1 : 비용 2
2 -> 1 : 비용 1

# n, m, cost 거꾸로 그래프
2 -> 1 : 비용 4
3 -> 1 : 비용 2
1 -> 3 : 비용 2
1 -> 2 : 비용 1

 

이후 거꾸로 뒤집어진 그래프를 사용하면 굳이 모든 마을에서 X 로 방문하는 것이 아니라 X 에서 다시 모든 마을에 대해서 다익스트라 알고리즘을 이용해서 최소 비용을 구하면 된다!!

 

결국 문제에서 제시하는 그래프를 단방향 그래프가 아닌 양방향 그래프로 만들어서 계산한다고 생각하면 편하다. 문제에서는 2->1 만 나타나지만 우리는 뒤집엇 2->1 의 값도 계산한 후 그래프를 만들어 2->1 로 이동가능하며, 1->2 로도 이동가능한 그래프를 만든다고 생각하자.

 

나머지는 주석 참고ㅠㅠ

사실 주석을 보는게 더 빠를듯

package baekJoon;


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

// https://www.acmicpc.net/problem/1238
// 총 2번의 다익스트라 알고리즘을 이용해서 풀이한다.

// 이때 첫번째는 x 에서 각 마을로 가는 최단 경로를 구하고,
// 두번째는 간선을 뒤집어서 각 마을에서 x 로 가는 최단 거리를 구한다.

// 결국 x 를 시작으로 하는 다익스트라 알고리즘 2번 돌리면
// x 에서 각 마을로 가는 최단 경로와 각 마을에서 x 로 가는 최단 경로가 각각
// goX 배열과 bakHome 에 저장된다.

// 이때 비용의 최대값을 구하는 것임으로 goX 배열과 bakHome 의 합을 구햇을 때 최대값을 확인하면 된다.
public class Quiz_1238 {
    static PriorityQueue<Party> q = new PriorityQueue<>((o1, o2) -> {
        return o1.cost - o2.cost;
    });

    // 각 마을 -> X 마을까지의 그래프
    static ArrayList<ArrayList<Party>> tree = new ArrayList<>();

    // X 마을 -> 각 마을까지의 그래프
    static ArrayList<ArrayList<Party>> treeReverse = new ArrayList<>();

    // X 로 가는 거리 배열 -> goX
    // X 에서 각 마을로 돌아오는 거리 배열 -> bakHome
    static int[] goX, bakHome;
    static int n, m, x;

    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());


        for (int i = 0; i <= n; i++) {
            tree.add(new ArrayList<Party>());
            treeReverse.add(new ArrayList<Party>());
        }

        goX = new int[n + 1];
        bakHome = new int[n + 1];

        Arrays.fill(goX, Integer.MAX_VALUE);
        Arrays.fill(bakHome, Integer.MAX_VALUE);

        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 cost = Integer.parseInt(st.nextToken());

            // tree 는 입력받은 그대로
            tree.get(from).add(new Party(to, cost));

            // treeReverse 는 입력받은 것을 반대로 -> 1 2 4 라면 2 1 4 로
            treeReverse.get(to).add(new Party(from, cost));

        }

        // 1. X 마을에서 각 마을까지 최단 거리 계산 후 bakHome 에 저장 => 파티 돌아오는 길
        findTime(tree, bakHome, x);

        // 2. 각 마을에서 X 마을까지의 최단 거리 계산 후 goX 에 저장 => 파티 가는 길
        findTime(treeReverse, goX, x);


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


    static void findTime(ArrayList<ArrayList<Party>> tree, int[] dis, int start ) {
        // 이미 방문한 곳을 체크하는 배열
        boolean[] visited = new boolean[n+1];

        // 시작지점은 언제나 X
        q.offer(new Party(start, 0));

        // 시작 지점이 되는 X 마을까지의 거리는 당연 0
        dis[start] = 0;

        // 여기서부터는 기본적인 다익스트라 알고리즘과 동일
        while (!q.isEmpty()) {
            Party p = q.poll();

            int nowTo = p.to;
            int nowCost = p.cost;

            if(visited[nowTo]) continue;

            visited[nowTo] = true;

            for (Party next : tree.get(nowTo)) {
                // 다음 방문할 마을인 nextTo 까지의 비용 값보다
                // 현재 마을까지의 비용+다음 마을까지의 비용이 더 작다면
                // dis[next.To] 를 변경
                if (dis[next.to] > nowCost + next.cost) {
                    dis[next.to] = nowCost + next.cost;

                    q.offer(new Party(next.to, nowCost + next.cost));

                }
            }
        }
    }

    // for 문을 사용해서 goX[i] + bakHome[i] 했을 때 최대값을 찾는 메서드
    static int findMax(){
        int result = Integer.MIN_VALUE;

        for(int i=1; i<=n; i++){
            result = Math.max(result, goX[i] + bakHome[i]);
        }

        return result;
    }

}

class Party {
    int to;
    int cost;

    Party(int to, int cost) {
        this.to = to;
        this.cost = cost;
    }

}

- Reference

https://pangtrue.tistory.com/272

[백준 1238 : JAVA] 파티 / 다익스트라

 

https://bcp0109.tistory.com/60

백준 1238번. 파티 (Java)

 

https://steady-coding.tistory.com/106

[BOJ] 백준 1238번 : 파티 (JAVA)