[이분탐색] 중량 제한

중량제한 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

128 MB

8711

1856

1182

24.049%

문제

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인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

3 3

1 2 2

3 1 3

2 3 2

1 3

예제 출력 1

3

출처

• 데이터를 추가한 사람: djm03178
• 문제의 오타를 찾은 사람: lg8375
• 빠진 조건을 찾은 사람: TAMREF

알고리즘 분류

• BFS
• 이분 탐색

이분 탐색 - 1 페이지

* 이분 탐색으로 풀 수 있다.

* DFS를 구현할 때, return DFS()와 같이 하지 않도록 주의. false 반환하게 되면 다음 노드를 탐색하지 못하고 계속 false만 반환하게 됨

 

#include <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))

#define MAX_EDGE_SIZE (200001)
#define MAX_VERTEX_SIZE (10001)

int start, end;

class Edge
{
public:
	int from;
	int to;
	int endurance;

	Edge() {
		from = to = endurance = 0;
	}

	bool operator<=(Edge other)
	{
		if (from == other.from) return to <= other.to;
		else return from <= other.from;
	}
};

class Graph
{
public:
	int V;
	int E;
	int cnt[MAX_VERTEX_SIZE];
	bool visited[MAX_VERTEX_SIZE];
	Edge edge[MAX_EDGE_SIZE];

	int ans = 0;

	Graph()
	{
		V = E = 0;
	}

	void initVisited()
	{
		for (register int i = 0; i <= V; i++) visited[i] = false;
	}

	void updateGraph()
	{
		E *= 2;
		mergeSort(0, E - 1);

		init();
		initVisited();

		for (register int i = 0; i < E; i++) cnt[edge[i].from]++;
		for (register int i = 1; i <= V; i++) cnt[i] += cnt[i - 1];
	}

	bool DFS(int node, int weight)
	{
		if (node == end) return true;
		visited[node] = true;

		for (int i = cnt[node - 1]; i < cnt[node]; i++)
		{
			int next = edge[i].to;
			if (visited[next]) continue;

			if (weight <= edge[i].endurance)
			{
				// return DFS()로 하면, false 리턴시 다음 노드를 탐색하지 못하고 주구장창 false만 반환하게 됨
				if(DFS(next, weight)) return true;
			}
		}

		return false;
	}

private:
	Edge tempEdge[MAX_EDGE_SIZE];

	void init()
	{
		for (register int i = 0; i <= V; i++) cnt[i] = visited[i] = 0;
	}

	void mergeSort(int start, int end)
	{
		if (start >= end) return;
		int mid = (start + end) / 2;

		mergeSort(start, mid);
		mergeSort(mid + 1, end);

		int i = start;
		int j = mid + 1;
		int k = 0;

		while (i <= mid && j <= end)
		{
			if (edge[i] <= edge[j]) tempEdge[k++] = edge[i++];
			else tempEdge[k++] = edge[j++];
		}

		while (i <= mid) tempEdge[k++] = edge[i++];
		while (j <= end) tempEdge[k++] = edge[j++];

		for (int i = start; i <= end; i++)
			edge[i] = tempEdge[i - start];
	}
};
Graph g;

int main(void)
{
	scanf("%d %d", &g.V, &g.E);

	for (register int i = 0; i < g.E; i++)
	{
		scanf("%d %d %d", &g.edge[i].from, &g.edge[i].to, &g.edge[i].endurance);

		g.edge[i + g.E].from = g.edge[i].to;
		g.edge[i + g.E].to = g.edge[i].from;
		g.edge[i + g.E].endurance = g.edge[i].endurance;
	}

	scanf("%d %d", &start, &end);

	g.updateGraph();

	int left = 1;
	int right = 1000000000;
	int ans = 0;

	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		g.initVisited();

		if (g.DFS(start, mid))
		{
			left = mid + 1;
			ans = MAX(ans, mid);
		}
		else
		{
			right = mid - 1;
		}
	}

	printf("%d\n", ans);


	return 0;
}