[백준 알고리즘][C++] 이분 탐색(binary search) - 1939번 중량제한

안녕하세요~

​

이번시간에는 1939번 중량제한 문제를 풀어보려고 합니다.

 

 

www.acmicpc.net/problem/1939

1939번: 중량제한

명심하셔야 될 것은 일단 문제를 풀기 전에 코딩을 먼저 시작하지 마시고, 반드시 연습장으로 생각을 정리하고! 이 후에 생각이 맞는 것 같다고 확신이 되면 그 때 코딩을 시작하세요. 코드를 작성하면서 문제를 풀게되면 정리가 안된 상태기 때문에 코드 수정이 잦아지고, 정신이 없어지게 됩니다ㅠㅠ

그러니 반드시 노트에 어떻게 풀 것인지에 대한 정리를 다 하시고 코딩을 시작하시기 바랍니다!!

​

binary search 공부에 좋은 문제입니다.

 

문제

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

정답 코드

#include <iostream>
#include <queue>
using namespace std;

#define VERTEX 100000
#define MAX 1000000000
typedef struct _Node {
	int vertex, cost;
	struct _Node* next;
}Node;
typedef struct _Graph {
	Node* adjlist[VERTEX+1];
}Graph;
int visit[10001];

int N,M;
int A, B, C;
int maxvalue = -1;
void addEdge(Graph* g, int from, int to, int cost)
{
	Node* newOne = (Node*)malloc(sizeof(Node));
	newOne->next = g->adjlist[from];
	newOne->vertex = to;
	newOne->cost = cost;
	g->adjlist[from] = newOne;
}
bool bfs(Graph* g, int pos, int pathMinVal)
{
	for (int i = 0; i <= N; i++)
	{
		visit[i] = 0;
	}
	bool ret = false;
	//pos에서 갈 수 있는 모든 경우 확인
	queue<int> q;
	q.push(pos);
	visit[pos] = 1;
	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		Node* pointer = g->adjlist[cur];
		while (pointer != NULL)
		{
			//도착했으면
			if (cur == B)
			{
				return true;
			}
			//pathMinVal보다 크면 갈 수 있는 곳
			if (pointer->cost >= pathMinVal && visit[pointer->vertex] == false)
			{
				visit[pointer->vertex] = true;
				q.push(pointer->vertex);
			}
			pointer = pointer->next;
		}
	}
	return false;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int MaxCost = -1;
	cin >> N >> M;
	Graph* graph = (Graph*)malloc(sizeof(Graph));
	for (int i = 1; i <= VERTEX; i++)
	{
		graph->adjlist[i] = NULL;
	}
	//초기화

	for (int i = 0; i < M; i++)
	{
		cin >> A >> B >> C;
		addEdge(graph, A, B, C);
		addEdge(graph, B, A, C);
		MaxCost = max(MaxCost, C);

	}
	int factoryA, factoryB;
	cin >> factoryA >> factoryB;

	int start = 1; 
	int end = MaxCost;

	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (bfs(graph, factoryA, mid))
		{
			start = mid + 1;
		} 
		else
		{
			end = mid - 1;
		}
	}
	cout << end << endl;
}