[백준 알고리즘] 1939번: 중량제한
March 17, 2021
https://www.acmicpc.net/problem/1939
문제
문제
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인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.
출력
첫째 줄에 답을 출력한다.
풀이
문제 분류에서 힌트를 얻어 풀 수 있었다. 일반적인 DFS로는 시간초과때문에 풀 수 없고, 이분탐색으로 최대 중량을 찾는 과정을 거쳐야 한다. 따라서 이분탐색으로 찾은 mid 값이 옮겨 볼 물품의 무게가 되고, dfs는 이 무게를 가지고 목적지 정점까지 도착이 가능한지 확인하는 용도로 사용된다.
처음 몇 번 동안 WA를 계속 받았는데, 그 이유는 dfs 의 재귀 호출 시에 그 결과를 그대로 return 해서 발생하는 문제였다. 이렇게 하면, 한 섬에 여러개의 다리가 있을 때, 하나의 다리만 확인하고 바로 그 결과를 return 하기 때문에 모든 가능한 경우를 다 확인할 수 없게 된다. 따라서 해당 무게로 목적지 도착이 성공했을 때만 바로 true를 반환하고 다른 경우들에는 continue로 다른 경우들까지 모두 확인하도록 하니 AC를 받았다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<vector<pair<int, ll>>> islands;
vector<bool> visited;
bool dfs(int start, int target, ll mid)
{
visited[start] = true;
if (start == target)
{
return true;
}
for (auto adj : islands[start])
{
int next = adj.first;
ll nextCost = adj.second;
if (!visited[next] && nextCost >= mid)
{
if (dfs(next, target, mid))
return true;
else
continue;
}
}
return false;
}
void clearVisit()
{
for (int i = 0; i < visited.size(); i++)
{
visited[i] = false;
}
}
int main()
{
int N, M;
ll maxWeight = 0;
int start, target;
cin >> N >> M;
islands.resize(N + 1);
visited.resize(N + 1, false);
for (int i = 0; i < M; i++)
{
int a, b;
ll c;
cin >> a >> b >> c;
islands[a].push_back({b, c});
islands[b].push_back({a, c});
maxWeight = max(maxWeight, c);
}
cin >> start >> target;
ll head = 0;
ll tail = maxWeight;
ll answer = 0;
while (head <= tail)
{
ll mid = (head + tail) / 2;
clearVisit();
if (dfs(start, target, mid))
{
answer = mid;
head = mid + 1;
}
else
{
tail = mid - 1;
}
}
cout << answer;
}
