[백준] 1939. 중량제한

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

 

 

🎯 문제 정리

1. 섬 N개가 다리로 연결되어 있고, 다리마다 최대 무게 제한이 있다. (2 ≤ N ≤10^4)
2. 섬A → 섬B로 짐을 옮길 때, 한 번에 옮길 수 있는 최대 무게를 구해야 한다.
3. 여러 경로가 있으면 전체 경로 무게는 그 경로에서 가장 작은 다리 무게 제한으로 결정된다. ⭐️
   이 때의 무게 제한을 구한다.

 

예시를 기반으로 흐름 정리

주어진 조건에 따르면, 1번 섬에 있는 공장에서 2번 섬에 있는 공장으로 가는 경로 중 최대로 짐을 실을 수 있는 경로를 찾고, 그 경로에서 요구하는 무게 제한을 반환해야 한다.

그러면 여기서 우선 순위를 생각해봤을 때, 어떤 섬A → 섬B 경로가 여러 개가 있을 경우 우선시되는 쪽은 경로 중 가장 많이 짐을 실을 수 있는 경로가 된다. 다시 말해 무게 제한이 큰 경로가 우선된다.

 

주어진 예를 기반해서 생각해보면:

1 → 2: 제한 2
1 → 3: 제한 3

1에서 바로 2로 가면 2톤, 3으로 가면 3톤이므로 1 → 3 경로가 우선된다.

1 → 2: 제한 2
3 → 2: 제한 5

하지만 1 → 3으로 갈 때 3톤까지만 가능했으므로 3 → 2의 5톤 다리는 의미가 없고 실제 제한은 3톤으로 결정된다.

1 → 2: 제한 2
1 → 3 → 2: 제한 3

즉 최종 비교는 위와 같다. 따라서 최적 경로는 1 → 3 → 2 (제한 3톤)이 된다.

 

구조화

🎯 `dp[i] = i번 섬까지 도달할 수 있는 최대 무게`
     처음에는 모든 섬의 값을 0으로 초기화하고, 출발 섬만 무한대로 설정한다.

• 모든 섬은 0으로 초기화:
  시작할 때는 아직 어떤 섬에도 건너가지 않은 상태이므로 기본값을 `짐을 안 옮긴 상태(0)`로 둔다.
  이후 경로를 따라가면서 단계적으로 값을 갱신한다.
• 출발 섬은 무한대(∞)로 초기화:
  출발하는 공장에서는 처음에 옮길 수 있는 짐의 양에 제한이 없다고 볼 수 있다. 하지만 실제로는 곧 다리를 건너야 하므로 그 순간 다리의 무게 제한에 맞춰 짐이 줄어든다.
  🤔 출발하는 공장에 엄청 많은 재고가 쌓여 있고, 다른 섬으로 옮기기 위해 다리를 건너게 되면서 그 다리가 버틸 수 있는 무게에 따라 짐을 덜어낸다고 생각했다.

섬의 최대 무게 업데이트 규칙

현재 섬 A에서 연결된 섬 B로 이동하려고 할 때:

1. 새로운 무게 제한은 `dp[A]와 다리(A-B)의 무게 제한 중 작은 값`이 된다.
   어떤 경로에서 옮길 수 있는 무게는 결국 경로를 구성하는 모든 다리의 제한 중 가장 작은 무게로 결정되기 때문에, 섬 A까지 옮겨올 수 있었던 무게(dp[A])와 새로 건너야 하는 다리의 무게 제한 중 더 작은 값으로 결정된다.
2. 만약 이 `새로운 무게 제한이 dp[B]보다 크다면`, 지금까지 알고 있던 B로 가는 최대 무게보다 더 많은 짐을 옮길 수 있는 새로운 경로를 찾은 것이므로 dp[B]를 갱신하고 방문 큐에 추가한다.

 

구현(1): 시간 초과 발생

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

/*
  N개 섬 (2~10^4) - 다리로 연결 (양방향, 같은 두 섬 사이 여러 다리 가능)
  섬 2개에 공장 
  공장 -> 공장 수송 -- 다리 중량 제한
  >>> 한 번 이동할 때 옮길 수 있는 중량 최댓값 
*/
public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken()); //섬
    int M = Integer.parseInt(st.nextToken()); //다리 
    
    //시작 섬:{연결 다리}
    Map<Integer, List<Bridge>> map = new HashMap<>();
    
    for(int i=0; i<M; i++) {
      st = new StringTokenizer(br.readLine());
      int node1 = Integer.parseInt(st.nextToken()); //섬1
      int node2 = Integer.parseInt(st.nextToken()); //섬2
      int weight = Integer.parseInt(st.nextToken()); //중량 제한
      
      //양방향
      map.computeIfAbsent(node1, k -> new ArrayList<>()).add(new Bridge(node2, weight));
      map.computeIfAbsent(node2, k -> new ArrayList<>()).add(new Bridge(node1, weight));
    }
    
    st = new StringTokenizer(br.readLine());
    int fac1 = Integer.parseInt(st.nextToken()); //공장1 
    int fac2 = Integer.parseInt(st.nextToken()); //공장2
    
    //공장1 -> 공장2로 가는 경로에서 최소 무게 제한 
    System.out.println(dj(N, map, fac1, fac2));
  }
  
  static int dj(int N, Map<Integer, List<Bridge>> map, int fac1, int fac2) {
    int[] dp = new int[N+1]; //0으로 초기화
    dp[fac1] = 1000000000; //출발지
    
    PriorityQueue<Bridge> pq = new PriorityQueue<>();  //더 큰 무게 우선 큐
    pq.offer(new Bridge(fac1, dp[fac1]));
    
    while(!pq.isEmpty()) {
      Bridge curr = pq.poll();
      
      if(map.get(curr.to) == null) continue;
      
      for(Bridge next : map.get(curr.to)) {
        //새로운 무게 제한: 현재 섬의 무게 제한과 현재 연결 다리의 무게 제한 중 더 작은 값 
        int newLimit = Math.min(curr.weight, next.weight);
        
        //새로운 무게 제한이 저장된 값(섬의 무게 제한)보다 클 경우에만 업데이트하고 방문 
        if(dp[next.to] < newLimit) {
          dp[next.to] = newLimit; 
          pq.offer(new Bridge(next.to, newLimit));
        }
      }
    }
    
    return dp[fac2];
  }
  
  static class Bridge implements Comparable<Bridge> {
    int to, weight;
    public Bridge (int to, int weight) {
      this.to=to; this.weight=weight;
    }

    //더 큰 무게 제한이 우선 
    @Override
    public int compareTo(Bridge b) {
      return b.weight - this.weight;
    }
  }
}

 

생각한 흐름대로 구현하니까 시간 초과가 발생했다. 

구현(2): 시간 초과 해결

`boolean[] visited`를 활용하여 섬 방문 여부를 기록한다.
어차피 각 섬에 도달할 때마다 더 많은 짐을 실을 수 있는 경로만 업데이트되므로 최초로 방문하는 순간 해당 섬까지의 최대 무게가 확정된다. 따라서 이미 방문한 섬은 더 이상 탐색하지 않도록 막아 불필요한 계산을 줄인다.

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

/*
  N개 섬 (2~10^4) - 다리로 연결 (양방향, 같은 두 섬 사이 여러 다리 가능)
  섬 2개에 공장 
  공장 -> 공장 수송 -- 다리 중량 제한
  >>> 한 번 이동할 때 옮길 수 있는 중량 최댓값 
*/
public class Main {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken()); //섬
    int M = Integer.parseInt(st.nextToken()); //다리 
    
    //시작 섬:{연결 다리}
    Map<Integer, List<Bridge>> map = new HashMap<>();
    
    for(int i=0; i<M; i++) {
      st = new StringTokenizer(br.readLine());
      int node1 = Integer.parseInt(st.nextToken()); //섬1
      int node2 = Integer.parseInt(st.nextToken()); //섬2
      int weight = Integer.parseInt(st.nextToken()); //중량 제한
      
      //양방향
      map.computeIfAbsent(node1, k -> new ArrayList<>()).add(new Bridge(node2, weight));
      map.computeIfAbsent(node2, k -> new ArrayList<>()).add(new Bridge(node1, weight));
    }
    
    st = new StringTokenizer(br.readLine());
    int fac1 = Integer.parseInt(st.nextToken()); //공장1 
    int fac2 = Integer.parseInt(st.nextToken()); //공장2
    
    //공장1 -> 공장2로 가는 경로에서 최소 무게 제한 
    System.out.println(dj(N, map, fac1, fac2));
  }
  
  static int dj(int N, Map<Integer, List<Bridge>> map, int fac1, int fac2) {
    int[] dp = new int[N+1]; //0으로 초기화
    dp[fac1] = 1000000000; //출발지
    
    boolean[] visited = new boolean[N+1];
    
    PriorityQueue<Bridge> pq = new PriorityQueue<>();  //더 큰 무게 우선 큐
    pq.offer(new Bridge(fac1, dp[fac1]));
    
    while(!pq.isEmpty()) {
      Bridge curr = pq.poll();
      
      //이미 방문했던 적 있는 섬이면 무시 
      if(visited[curr.to]) continue;
      
      //방문한 적 없으면 방문 처리 
      visited[curr.to] = true;
      
      //공장2에 도착했으면 종료 
      if(curr.to == fac2) return dp[fac2]; 
      
      
      if(map.get(curr.to) == null) continue;
      for(Bridge next : map.get(curr.to)) {
        //새로운 무게 제한: 현재 섬의 무게 제한과 현재 연결 다리의 무게 제한 중 더 작은 값 
        int newLimit = Math.min(curr.weight, next.weight);
        
        //새로운 무게 제한이 저장된 값(섬의 무게 제한)보다 클 경우에만 업데이트하고 방문 
        if(dp[next.to] < newLimit) {
          dp[next.to] = newLimit; 
          pq.offer(new Bridge(next.to, newLimit));
        }
      }
    }
    
    return dp[fac2];
  }
  
  static class Bridge implements Comparable<Bridge> {
    int to, weight;
    public Bridge (int to, int weight) {
      this.to=to; this.weight=weight;
    }

    //더 큰 무게 제한이 우선 
    @Override
    public int compareTo(Bridge b) {
      return b.weight - this.weight;
    }
  }
}