[백준] 1939 - 중량제한

[문제링크]

1939번: 중량제한

 

0. 다익스트라나 프림에서 사용하는 방식을 사용했다.

 

1. 시작지점의 초기값은 MAX, 나머지 지점의 초기값은 0

 

2. 아직 가보지 못한 지점중, 가장 많은 짐을 지고 갈수있는 지점 X를 탐색한다

 

3. X로부터 갈수있는 지점들을, X를 거치는 경우 / 기존 최댓값을 비교해 갱신한다

 

4. 이를 n번 반복하면, n개의 노드 전체를 탐색한 것이다.

 

5. 종료된 후 end지점에 있는 값이 해당 지점에 들고갈 수 있는 최대 짐 무게이다

 

* 성능 향상법 : n에 비해 m의 크기가 크지 않으므로, 우선순위 큐를 이용해 최대값을 찾는다면 시간 성능이 올라갈 것이다

 

* 다른 풀이법 : 짐의 무게가 N일때, cost가 N 이상인 다리만 사용해서 시작점 - 도착점에 도달할 수 있는 최대 N 구하기

  - N에 대해 bfs를 실행해보며 이분탐색으로 N값을 갱신한다

 

* 문제 태그에 disjoint set이 있던데.. 모르겠다 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		ArrayList<ArrayList<int[]>>graph=new ArrayList<>();
		
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int n1 = pint(st.nextToken());
			int n2 = pint(st.nextToken());
			int c = pint(st.nextToken());
			graph.get(n1).add(new int[] {n2,c});
			graph.get(n2).add(new int[] {n1,c});
		}

		st = new StringTokenizer(br.readLine(), " ");
		int fst = pint(st.nextToken());
		int end = pint(st.nextToken());
		
		//각 지점까지 도달할 수 있는 최대 무게, 초깃값 0
		int[]weight = new int[n+1];
		boolean[]isV=new boolean[n+1];
		weight[fst]=Integer.MAX_VALUE;
		
		for (int i = 0; i < n; i++) {
			int max=0,maxNode=0;
			for (int j = 0; j <= n; j++) {
				if(!isV[j] && max<weight[j]) {
					max=weight[j];
					maxNode=j;
				}
			}
			
			isV[maxNode]=true;
			
			for (int j = 0; j < graph.get(maxNode).size(); j++) {
				int[]next = graph.get(maxNode).get(j);
				int nextCost=Math.min(next[1], weight[maxNode]);
				
				if(weight[next[0]] <nextCost) {
					weight[next[0]]=nextCost;
				}
			}
		}
		System.out.println(weight[end]);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면