[백준]JAVA - 1939번: 중량제한

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

1939번: 중량제한

🔶 풀이

한 번의 이동에서 옮길 수 있는 물품들의 최대값을 구하시오.

가능한 최대 중량을 찾기 위해서는 bfs로만 풀 수 없고, 이진 탐색을 이용해야한다.

 

1. 입력하는 과정에서 min, max 값을 선언해주고, 다리는 양방향이므로 arrList에 두 번씩 입력해준다.

for (int i=0; i<M; i++) {
    st = new StringTokenizer(br.readLine());
			
    int s = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
			
    max = Math.max(max, v);
    min = Math.min(min, v);
			
    arrList[s].add(new Bridge(e, v));
    arrList[e].add(new Bridge(s, v));
}

2. 모든 입력을 완료했으면 min, max 값으로 이진 탐색을 진행한다.

: 중량(mid)를 기준으로 해당 경로를 이용할 수 있는지 여부를 따지면서 진행하면 된다.

 

이동할 수 없음 → 중량이 너무 크다는 뜻이므로 max - 1

이동할 수 있음 → 중량이 너무 작다는 뜻이므로 min + 1, 또한 이동할 수 있는 값이므로 ans 초기화

 

3. 해당 경로를 이용할 수 있는지 여부는 bfs로 진행한다.

: 해당 경로를 안전하게 이용할 수 있다면 true를 반환해주고, 그렇지 않다면 false를 반환해준다.

// 현재 섬에서 갈 수 있는 섬 개수만큼
for (int i=0; i<arrList[now].size(); i++) {
            
    // 다리를 건널 수 있고, 도착 섬에 방문하지 않은 경우
    if (arrList[now].get(i).weight >= w && !visited[arrList[now].get(i).endLand]) {
        visited[arrList[now].get(i).endLand] = true;
        q.add(arrList[now].get(i).endLand);
    }
}

재방문 방지를 위해서 visited[] 배열도 선언해주어야함.

 

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static ArrayList<Bridge>[] arrList; // 다리 정보를 담는 배열
    static int N, M;
	
    public static class Bridge {
        int endLand, weight;
		
        public Bridge(int endland, int weight) {
            this.endLand = endland;
            this.weight = weight;
        }
    }
	
    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()); // 다리에 대한 정보
		
        arrList = new ArrayList[N+1];
        for (int i=0; i<=N; i++) {
            arrList[i] = new ArrayList<>();
        }
		
        int max = 0;
        int min = Integer.MAX_VALUE;
		
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
			
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
			
            max = Math.max(max, v);
            min = Math.min(min, v);
			
            arrList[s].add(new Bridge(e, v));
            arrList[e].add(new Bridge(s, v));
        }
		
        st = new StringTokenizer(br.readLine());
        int sLand = Integer.parseInt(st.nextToken()); // 출발 섬
        int eLand = Integer.parseInt(st.nextToken()); // 도착 섬
		
        int ans = 0;
        while (max >= min) {
            int mid = (max + min) / 2; // 현재 중량 
			
            // 현재 중량(mid)로 출발 섬에서 도착 섬으로 갈 수 있는지 여부
            if (canGo(sLand, eLand, mid)) {
                min = mid + 1;
                ans = mid;
            } else {
                max = mid - 1;
            }
        }
		
        System.out.println(ans);
    }
	
    /**
	 * 
	 * @param s 출발 섬
	 * @param e 도착 섬
	 * @param w 현재 중량
	 * @return
	 */
    public static boolean canGo(int s, int e, int w) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N+1];
		
        q.add(s);
        visited[s] = true;
		
        while (!q.isEmpty()) {
            int now = q.poll();
			
            // 도착할 경우
            if (now == e) {
                return true;
            }
			
            // 현재 섬에서 갈 수 있는 섬 개수만큼
            for (int i=0; i<arrList[now].size(); i++) {
            
                // 다리를 건널 수 있고, 도착 섬에 방문하지 않은 경우
                if (arrList[now].get(i).weight >= w && !visited[arrList[now].get(i).endLand]) {
                    visited[arrList[now].get(i).endLand] = true;
                    q.add(arrList[now].get(i).endLand);
                }
            }
        }
		
        return false;
    }
}