[1939] 중량제한 - Java[자바]

 

 

| 문제 링크

 

 

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

1939번: 중량제한

 

 

 

 

 

---

 

 

 

 

 

| 문제

 

 

1. N개의 섬(노드)와 M개의 다리(간선)의 정보가 주어집니다. N(2 ≤ N ≤ 10,000) , M(1 ≤ M ≤ 100,000)
2. 두 개의 공장은 서로 다른 섬에 있으며, 공장까지 갈 수 있는 다리는 반드시 존재합니다.
3. M개의 간선의 정보에는 A, B, C 세 가지 값이 주어지며, A와 B는 섬번호, C는 두 섬 사이에 있는 다리가 견딜 수 있는 무게를 나타냅니다(양뱡향).
4. 다리마다 무게가 제한되기에 최대로 옮길 수 있는 무게를 구하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

 

1. 처음에는 다이크스크라를 이용해 최대로 이동할 수 있는 무게(Math.min을 활용)를 구하려 했으나, 메모리 초과가 발생했습니다.
2. 도로의 무게를 min 값과 max값을 저장해 이분 탐색을 진행했으며, mid 값의 무게가 공장 간의 모든 다리를 통과할 수 있는지 확인하는 BFS 탐색을 했습니다.
3. 이때 주의할 점은 이분 탐색의 조건 whlie(minCost<=maxCost)의 조건과 maxCost를 출력한다는 점 입니다.

while(minCost<=maxCost) {
    int mid = (minCost+maxCost) >>> 1;
    //mid에 대해 통과 가능하면 mid를 min값으로 다시 이분탐색
    if(bfs(mid))
        minCost = mid+1;
    //mid에 대해 통과하지 못한다면 max 값을 mid-1로 다시 이분탐색
    else
        maxCost = mid-1;
}

       다리의 무게가 1, 2, 3이 있으며, 공장 간 이동에 최소 무게가 2인 경우
       첫 번째, mid 값은 2로 min, max의 값이 3이 됩니다.
       하지만 3이 실제로 가능한 무게인지 BFS를 동작하지는 않은 상태입니다. 따라서 minCost==maxCost인 경우도
       공장 간 이동이 가능한지 마지막 탐색을 진행하며, 만약 불가능한 경우 -1을 해준 maxCost 값을 출력해줍니다.

 

 

 

 

---

 

 

 

 

| 코드

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Node1939 {
	int to;
	int w;

	public Node1939(int to, int w) {
		this.to = to;
		this.w = w;
	}
	
}

public class Main {
	
	public static int n,s,e;
	public static List<Node1939>[] list;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		for(int i = 1; i<=n; i++) {
			list[i] = new ArrayList<>();
		}
		
		//인접리스트 생성
		int minCost = Integer.MAX_VALUE;
		int maxCost = 0;	
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			minCost = Math.min(minCost, c);
			maxCost = Math.max(maxCost, c);
			list[a].add(new Node1939(b,c));
			list[b].add(new Node1939(a,c));
		}
		
		st = new StringTokenizer(br.readLine());
		s = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		//<=이며, maxCost를 반환하는 이유는 다음과 같다
		//다리의 무게가 1, 2, 3이며 공장간의 이동이 무게 2까지 가능한 경우
		//처음 mid는 2로 while절을 무사히 통과하며, 2, 3의 mid 값이 2로 통과하며, minCost가 3이된다.
		//만약 minCost<maxCost이며, minCost를 출력하는 경우 답은 3으로 출력된다.
		//즉 minCost와 maxCost가 동일한 경우도 최종적으로 해당 무게가 다리를 지나갈 수 있는지 확인한 수 값을 반환한다.
		while(minCost<=maxCost) {
			int mid = (minCost+maxCost) >>> 1;
			//mid에 대해 통과 가능하면 mid를 min값으로 다시 이분탐색
			if(bfs(mid))
				minCost = mid+1;
			//mid에 대해 통과하지 못한다면 max 값을 mid-1로 다시 이분탐색
			else
				maxCost = mid-1;
		}
		bw.write(String.valueOf(maxCost));
		br.close();
		bw.close();
		
	}
	
	public static boolean bfs(int cost) {
		boolean[] flag = new boolean[n+1];

		Queue<Node1939> que = new LinkedList<>();
		que.add(new Node1939(s,cost));
		
		
		while(!que.isEmpty()) {
			Node1939 now = que.poll();
			int from = now.to;
			
			//이미 방문한 다리인 경우 continue;
			if(flag[from])
				continue;
			flag[from] = true;
			
			//도착지에 도착한 경우 true 반환
			if(from == e)
				return true;
			
			for(Node1939 next : list[from]) {
				int to = next.to;
				int nextW = next.w;
				if(flag[to] || cost>nextW)
					continue;
				
				que.add(new Node1939(to,nextW));
			}
		}
		
		//다 지나도 도착지에 도달하지 못한 경우 false 반환
		return false;
	}

}