[백준 / Java] 1939번: 중량제한 (골드3)

문제 풀이 날짜: 2023.10.13
포스트 작성일: 2023.10.16

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1939번: 중량제한 (골드3)

 

키워드

다익스트라

 

풀이 접근법

• 서로 다른 두 공장 A, B가 있다고 할 때, A → B로 이동하는 모든 경로(직+간접) 중에서 ‘최대 하중’을 구하는 문제이다. 따라서 다익스트라로 풀이하였다.
• 단, 전체 경로 중에서 건너게 되는 다리마다의 최대 하중은 각기 다르며, 그 다리 중 가장 버틸 수 있는 무게가 적은 쪽을 기준으로 맞추어야 한다. 따라서 경로 중 경유하는 간선 중 가장 가중치가 작은 간선을 ‘하중’으로 택한다.
•  가중치 큰 간선을 우선 선택한다. pq에는 무게가 큰 순서대로 Node를 넣어야 한다. (내림차순 정렬) ⇒ 가능한 하중이 큰 경로를 찾아야 하므로
• 현재까지의 최대 하중보다 작으면 가지치기한다 ⇒ 그 경로에서는 최대 하중보다 큰 짐을 수송할 수 없으므로

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {

	private static List<Node>[] graph;
	private static int[] maxWeight;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] temp = br.readLine().split(" ");

		int N = Integer.parseInt(temp[0]); // 섬의 개수
		int M = Integer.parseInt(temp[1]); // 다리의 개수

		graph = new LinkedList[N + 1];
		maxWeight = new int[N + 1]; //dist 배열

		for (int i = 1; i <= N; i++) {
			graph[i] = new LinkedList<>();
			maxWeight[i] = -1;
		}

		for (int i = 1; i <= M; i++) {
			temp = br.readLine().split(" ");

			int A = Integer.parseInt(temp[0]);
			int B = Integer.parseInt(temp[1]);
			int C = Integer.parseInt(temp[2]);

			graph[A].add(new Node(B, C)); // 양방향
			graph[B].add(new Node(A, C));
		}

		temp = br.readLine().split(" ");
		int start = Integer.parseInt(temp[0]);
		int end = Integer.parseInt(temp[1]);

		int maxWeight = dijkstra(start, end);

		System.out.println(maxWeight);
	}

	private static int dijkstra(int start, int end) {
		PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.weight, o1.weight)); // 가중치 큰 간선 우선

		maxWeight[start] = Integer.MAX_VALUE;
		pq.add(new Node(start, maxWeight[start]));
		
		// Node에 기록된 '최소' 중량 중 최대인 것을 찾는다.
		while (!pq.isEmpty()) {
			Node n = pq.poll();

			// 현재까지 구해진 최대값보다 작으면,
			// 즉 n까지 도달하는 데 소모되는 weight가 유망하지 않으면 가지치기
			if(n.weight < maxWeight[n.num]) {
				continue;
			}

			for (Node next : graph[n.num]) {
				int currWeight = Math.min(n.weight, next.weight); //이 경로의 하중
				if (currWeight > maxWeight[next.num]) { //더 큰 것으로 교체될 수 있다면 add
					maxWeight[next.num] = currWeight;
					pq.add(new Node(next.num, maxWeight[next.num]));
				}
			}
		}

		return maxWeight[end];
	}

}

class Node {
	int num; // 현재 노드 번호
	int weight; // 해당 경로까지의 '최소' 중량

	public Node(int num, int weight) {
		this.num = num;
		this.weight = weight;
	}
}

---