[백준] 1939 중량제한

ack·2021년 1월 25일

Algorithm Study

목록 보기

8/21

📌 문제

N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

✔ 입력

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

✔ 접근방법

리스트를 이용하여 그래프를 입력받는다
입력 조건을 보면 N의 개수도 10,000개로 이차원 배열을 생성하면 배열의 크기는 10,000 * 10,000 으로 메모리 초과가 발생한다.
중량 제한을 설정하여 이분탐색을 진행한다.
이분 탐색을 이용하여 중량 제한 값을 설정하고 해당 중량 제한 값으로 목적지에 도달 할 수 있는 경우가 한번이라도 있으면 다음 탐색이 진행하지 않도록 DFS를 코드를 작성하였다.
또한, 현재의 중량제한(mid)값으로 목적지에 달성할 수 있으면 mid의 값을 증가하고, 목적지에 달성할 수 없으면 mid의 값을 감소하여 DFS를 탐색하는 방법을 통해 최적의 값을 알아낼 수 있다.

✔ 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

//1939 중량제한
public class Main {

	static class Node {
		int y;
		long c;

		Node(int y, long c) {
			this.y = y;
			this.c = c;
		}
	}

	static ArrayList<ArrayList<Node>> al = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();

		boolean[] visit = new boolean[n];
		long max = 0;
		long answer = 0;

		for (int i = 0; i < n; i++) {
			al.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			long c = sc.nextInt();

			al.get(x).add(new Node(y, c));
			al.get(y).add(new Node(x, c));

			max = Math.max(max, c);
		}

		// 시작
		int a = sc.nextInt() - 1;
		// 끝
		int b = sc.nextInt() - 1;

		long start = 0;
		long end = max;

		while (start <= end) {
			long mid = (start + end) / 2;
			if (dfs(visit, n, a, b, mid)) {
				answer = mid;
				start = mid + 1;
				// System.out.println(answer);
			} else
				end = mid - 1;
			Arrays.fill(visit, false);
		}

		System.out.println(answer);
	}

	//방문여부배열, 노드의 수, 현재값, 목적지, 최소값
	private static boolean dfs(boolean visit[], int n, int now, int b, long mid) {
		// 방문처리함
		visit[now] = true;

		if (now == b) {
			return true;
		}

		for (Node node : al.get(now)) {
			if (node.c >= mid && !visit[node.y]) {
				if (!dfs(visit, n, node.y, b, mid))
					continue;
				else
					return true;
			}
		}
		return false;
	}
}