1. 문제 설명 📌

문제 링크

가중치 양방향 그래프가 주어질 때, 출발지에서 도착지 까지 한번의 이동으로 가져갈 수 있는 물건의 최대 중량을 구하여라.

2. 접근 방식 🗃️

KEY WORD: Parametric Search, Binary_Search,DFS

(1) 가중치 양방향 그래프를 인접리스트로 구현한다.
(2) 이분탐색을 활용해, 한번에 옮길 수 있는 물건의 최대 중량을 구한다. (이분 탐색은 다음과 같이 진행 된다.)
- a. 문제에서 주어진 최대 중량과 최소 중량을 활용해 중앙값을 구한다.
- b. 해당 중앙값을 한 번에 옮길 수 있는 최대 중량이라 쳤을 때, 도착지까지 옮기는 게 가능한지 확인한다.
- c-1. 가능하다면 최소 중량을 현 중앙값 + 1 올려서, 다음에 구할 중앙값을 상향 조정 한다.
- c-2 .불가능하다면 최대 중량을 현 중앙값 - 1으로 내려서 다음에 구할 중앙값을 하향 조정한다.
- d. 최대 중량과 최소 중량이 엇갈릴 때까지 a부터 반복한다.
(3) (2)-b를 구하기 위해 DFS를 활용한다. 출발지에서 시작해서, 도착지까지 현 최대 중량 d를 모두 들고 갈 수 있다면 true, 안된다면 false를 반환한다.

(1) Parametric Search 활용점 ✨

한 번에 옮길 수 있는 물건의 최대 중량 = 도착지로 가는 루트마다의 간선 가중치 최소값 들 중 최대값 이다.

다음과 같이 존재하는 그래프에서 출발지는 NODE 1, 도착지는 NODE 4라고 해보자.

그러면 갈 수 있는 루트는 3가지 이다.

여기서 각 루트마다 자신에게 속하는 가중치 중 최소값을 표시해보면,

각각 3,2,4 이고, 한 번에 움직임으로 최대한 많은 물건을 옮기려면, 초록색 루트를 골라서 4개 옮겨야 한다.

이러한 최적화 문제를 DFS로만 풀려면 되게 복잡해진다. 그 이유는

(a) 루트가 몇 개가 나올 수 있는지 알 길이 없다.
(b) (a)번 때문에 지금까지 구한 루트의 간선 최소값 중에서 최대값이 진짜 최대값이라고 확신할 수 없다.

이러한 이유 때문에 최적화 문제를 여러 개의 결정 문제로 바꾸어 풀겠다. (Parametric Search)

여기서는 f(w) = 최소 하나의 루트라도 용량 W를 한 번에 옮길 수 있으면 true, 안되면 false 반환 을 활용한다.

그러면 위의 예시처럼 여러개의 f(w)를 얻을 수 있을 것이고, 우리는 true가 나온 값들 중 제일 오른쪽 값의 w를 출력하면 된다.

예시는 f(d)의 배열 전체를 구해야 하는 것처럼 들었지만 최소용량부터 최대용량까지 모든 f(w)를 구할 필요는 없다. 왜냐면, 이분 탐색을 통해, 답이 될 수 없는 후보 군을 효과적으로 제거해 나가면 되기 때문이다. 이는 f(w)의 반환값의 모음이 단조적인 성격을 띄기 때문에 가능하다.

즉, f(3) = true면 f(0) ~ f(2) = true임이 보장된다. (가중치 3을 옮길 수 있는데, 0 ~ 2는 무조건 되기 때문)
반대로 말하면 f(11) = false 이면, f(12) ~ f(1000000000) = false 이다.

(2) DFS 구현 ✨

현재 갈려는 가중치가 이분탐색으로 구한 mid 값보다 작다면 현재 도착지로 보내려는 최대 중량을 보낼 수 없다는 뜻이다. 이 경우 방문하지 않고 지나간다.

DFS를 다 돌렸을 때, 도착지에 도착 했으면. (방문 표시 남기기) true 반환하고, 안되면 false를 반환하면 된다.

3. 코드 소개 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int N, M, START_POINT, END_POINT;
    static int MAX_WEIGHT;
    static boolean isValid = false;
    static Island [] islands;
    static boolean [] isVisited;
    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());
        islands = new Island [N + 1];
        isVisited = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            islands[i] = new Island();
        }
        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 weight = Integer.parseInt(st.nextToken());
            islands[start].add(end, weight);
            islands[end].add(start, weight);
            MAX_WEIGHT = Math.max(MAX_WEIGHT, weight);
        }
        st = new StringTokenizer(br.readLine());
        START_POINT = Integer.parseInt(st.nextToken());
        END_POINT = Integer.parseInt(st.nextToken());
        System.out.println(binary_search());
    }

    public static int binary_search() {
        int start = 1;
        int end = MAX_WEIGHT;
        while (start <= end) {
            isVisited[START_POINT] = true;
            int mid = start + (end - start)/2;
            f(START_POINT, mid);
//            System.out.println(isValid);
            if(isValid) start = mid + 1;
            else end = mid - 1;
            Arrays.fill(isVisited, false);
            isValid = false;
        }
        return start-1;
    }

    public static void f(int v, int min_weight) {
//        System.out.printf("NOW NODE: %d \n", v);

        // 기저 조건
        if(v == END_POINT) return;
        // 계산
        for(int key : islands[v].keySet()){
            if(!isVisited[key]){
                if(islands[v].get(key) < min_weight) continue; // 최소 중량으로 갈 수 없으면 넘어간다.
                isVisited[key] = true;
//                System.out.printf("NEXT NODE: %d isVisited: %s \n", key, Arrays.toString(isVisited));
                if(isVisited[END_POINT]) isValid = true;
                f(key, min_weight);
                if(isValid) return;
            }
        }
    }
}

class Island {
    HashMap<Integer, Integer> arrivals;

    public Island () {
        arrivals = new HashMap<>();
    }

    public void add (int v, int w) {
        if(arrivals.containsKey(v)){
            if(arrivals.get(v) < w) arrivals.put(v,w);
        }else{
            arrivals.put(v, w);
        }
    }

    public Set<Integer> keySet() {
        return arrivals.keySet();
    }

    public int get(int v) {
        return arrivals.get(v);
    }

    public String toString() {
        return arrivals.toString();
    }
}

4. 배운 것들 🎯

DFS에 STACK을 썼다면...✨

나는 DFS를 재귀로 구현 했으나, 만약 STACK으로 구현 했다면, 방문 배열이나 isValid가 모두 DFS 함수 내에서 처리가 되므로 훨씬 코드가 깨끗하고 가독성이 높았을 것 같다.

방문 처리에 대하여 ✨

내가 처음에 틀린 이유는, 방문 처리한 노드를 다른 루트로 또 올 수 있지 않을까 싶어서 DFS가 끝난 이후에 다시 미방문으로 방문 여부를 바꾸었다. 하지만, 나는 최적화 문제를 용량 w를 도착지까지 가져갈 수 있는가? 라는 결정 문제로 바꾸었기 때문에, 어느 루트로 가도 도착지만 가면 되기 떄문에 True 처리가 이미 된 노드를 false로 바꿀 필요가 없다.