[백준] Q11085 군사 이동 JAVA

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

11085번: 군사 이동

1. 문제의 유형 및 이해

그래프 탐색, 분리집합

문제를 단순히 하면 다음과 같습니다.

노드 P개와 W개의 edge가 주어진다. 이 때 두 노드 C와 V가 주어지는데,

C에서 V까지 가는 여러 경로가 있다.

이 때 각 경로에 포함된 간선 중 가장 작은 값을 가장 크게하는 경로를 찾아보자.

 

처음에 푼 풀이방법과 이후에 알게된 풀이에 대해 정리해봅시다.

2. 문제 접근 방법

처음 접근 방법

여러 가지 생각을 하다가 증명을 잘못해서 결국 완전탐색해야되는거 아니야? 라고 생각했고, 너무 많기 때문에 최단거리와 비슷하게 dp를 활용해보자 라고 생각했습니다.

연결된 두 노드 i와 j에 대해서 dp[i]를 i 까지 오는 가장 좁은 길 중 가장 큰 값이라고 생각해보면,

update되는 값은 i까지 올 때의 값 (dp[i])과 

i~j까지 연결된 가중치 weight[i][j] 중 min 값으로 update를 해주어야합니다.

(연결된 간선 들 중 가장 작은 가중치 값)

min = Math.min(dp[i], weight[i][j]);

그렇게 되었을 때 dp[j] = Math.max(dp[j], min) 으로 정의할 수 있습니다.

(중에서 가장 큰 값)

 

dp[start][end]로 정의할 수 있지만, start는 명시적으로 C로 주어지기 때문에 생략하고 dp[end]로 정의할 수 있고 

dp[i]는 C부터 i까지 도달하는 경로에서 가장 작은 값들 중 가장 큰 값.으로 정의할 수 있습니다.

 

BFS로 그래프를 탐색하면서 가려고하는 노드 J에 대해

dp[j]보다 현재까지 온 min값이 더욱 큰 경우 업데이트하고 방문할 수 있습니다.

package DayByDay._0324;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @author : pcrmcw0486
 * @문제번호 : Q11085
 * @문제이름 :군사 이동
 * @난이도 : Gold III
 * @date : 2022-03-24 오후 4:38
 * @문제이해 BW - CW  p개의 지점과 wㄱ의 길로 표현된다.
 * 모든 길은 양방향, 길마다 너비가 존재하여 비례하는 수의 군사가 지나갈 수 있다.
 * BW : 뭉치는 것이 유ㅜ리하다, 경로는 정해두고, 경로로만 모든 군사를 보냄.
 * BW : 경로 상 길 중 가장 너비가 좁은 길의 너비를 최대화 하는 경로.
 * c ,v 가 주어질 떄, c->v로 가는 경로 중 가장 좁은 너비가 가장 크도록 하는 경로.
 * V(1000) E(50000) edge가 5만개, V가 1000개.
 * @알고리즘
 * @접근방법
 */
public class Main {
    //static ArrayList<Edge>[] graph;
    static ArrayList<Edge>[] graph;
    static int[] dp;
    static int P, W, C, V;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        P = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        graph = new ArrayList[P];
        for (int i = 0; i < P; i++) graph[i] = new ArrayList<>();

        dp = new int[P];
        dp[C] = Integer.MAX_VALUE;
        for (int i = 0; i < W; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            graph[u].add(new Edge(v, d));
            graph[v].add(new Edge(u, d));
        }
        int[] dp = new int[P];
        dp[C] = Integer.MAX_VALUE;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(C);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int min;
            for (Edge e : graph[cur]) {
                min =e.dist;
                if(dp[cur] != 0) min = Math.min(dp[cur], min);
                if (dp[e.to] < min) {
                    dp[e.to] = min;
                    queue.add(e.to);
                }
            }
        }
        System.out.println(dp[V]);
    }


    private static class Edge {
        int to, dist;

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

 

이후의 풀이

문제 분류로 '분리 집합' 이 있어 다시 한번 생각해 보았습니다.

처음에 생각못한 증명은 다음과 같은 그림이 있을 때 어떻게든 V까지 가려고 할 때 항상 큰 edge만 선택하는 것이 옳은가라고 생각하여 접근했습니다.

노드를 기준으로 보자면 5를 선택하고 1을 선택하여 그렇지 않은 것 처럼 보입니다.

Krsukal과 같은 spanning tree처럼 edge를 기준으로 생각해봅시다.

spanning tree에서는 모든 노드들이 연결되게 됩니다.

이렇게 되면 C와 V가 같은 노드에 들어오는 순간 경로가 하나 생기게 되는 것이고, 우리는 큰 edge들을 기준으로 spanning tree를 연결해왔기 때문에 C와 V로 가는 가장 작지만 큰 값을 가질 수 있습니다.

edge가 큰 값으로 묶어가는 과정.

얻어가는 점

edge가 퍼질 때 노드를 기준으로 볼 것인가 edge를 기준으로 볼 것인가 생각해볼 문제입니다.

최단거리의 경우에도 edge를 기준으로 볼 수 있는 bellman ford와 노드를 중심으로 보는 dijkstra가 있고

최소 스패닝 트리의 경우에도 edge를 기준으로 Kruskal이 node를 중심으로 Prim 알고리즘이 있듯이, 

edge relaxation에 대해 여러 관점으로 접근해야 한다는 점을 얻어갑니당.

 

그래프 경로들을 모두 봐야한다는 생각에 BFS나 DFS로만 생각했던 것이 조금 아쉬웠던 것 같습니다.