백준 1939 중량제한 C++ /Java

예제를 그려보면 다음과 같이 그릴 수 있다.

처음에는 문제를 읽고 1번섬에서 3번섬으로 이동시 최대 옮길 수 있는 중량은 최대 4(1번섬에서 2번섬으로 이동시 2, 2번섬에서 3번섬으로 이동시 2, 토탈 4) 아닌가? 라고 생각했다.

 

문제를 다시 읽어보니, "한번의 이동에서 옮길 수 있는" 이라는 조건이 있었고 이를 이용하여 최단거리를 물어보는 문제라는것을 파악할 수 있었다.  최단거리 알고리즘(해당 문제에서는 BFS 또는 DFS을 이용)을 이용하여 최대 무게로 갈 수 있는지 없는지 검사하면 된다. 여기서 문제를 다시 읽어보면, 두 도시 사이에 여러개의 다리가 있을 수 있다고 하였으니, 최대 무게보다 크거나 같은 크기의 최대 중량에 해당하는 간선만 검사해주면 된다.

 

그런데 여기서 끝이 아니다! 아직 최대 무게를 결정해야하는 단계가 남아있다. 다리를 지날 수 있는 최대 무게는 이분탐색을 이용하여 구해주면 된다. 중량제한은 "기준"이라는것을 의미하고 중량제한보다 작거나 같은 값은 모두 다 이동할 수 있고 큰 값은 절대 이동할 수 없기 때문이다.

 

다시정리해서 말해보면, 아래와 같다.

 

1. 이분탐색을 이용해서 다리가 갖는 최소 중량 Mid 값을 정한다.

2. dfs를 이용하여 섬과 섬 사이의 연결 여부를 확인하고, 연결된 섬과 섬의 중량이 Mid 보다 작으면 건너지 않는다. (최대 중량을 구해야하기 때문에 섬과 섬 사이의 중량이 다리가 갖는 최소 중량인 Mid 값보다 작으면 굳이 건너야할 필요가 없다.)

3. 문제에서 주어진 목적지 섬까지 도달했다면, 다리가 갖는 최소 중량 Mid 값을 늘려야 한다는 말이다. (최대값에 도달하지 못했기때문)

4. 문제에서 주어진 목적지 섬까지 도달하지 못했다면, 다리가 갖는 최소 중량 Mid값을 줄여야 한다는 말이다.(최대값을 넘어섰기때문)

 

코드(C++)

#include <iostream>
#include <vector>

using namespace std;

int n, m, a, b, c, startVer, endVer, ans, visited[10001];
vector<pair<int, int>> v[10001];

void input()
{
    cin >> n >> m;
    while(m--)
    {
        cin >> a >> b >> c;
        v[a].push_back({b,c});
        v[b].push_back({a,c});
    }
    cin >> startVer >> endVer;
}

bool go(int vertex, int mid)
{
    if(visited[vertex])
        return false;
    
    if(vertex == endVer)
        return true;
    
    visited[vertex] = 1;
    for(const auto& pos : v[vertex])
    {
        int next = pos.first;
        int cost = pos.second;
        if(cost >= mid)
        {
            if(go(next, mid))
                return true;
        }
    }

    return false;
}

void binararySearch()
{   
    int lo = 1, hi = 1000000000;
    while(lo <= hi)
    {
        fill(visited, visited+10001, 0);
        int mid = (lo + hi) / 2;
        if(go(startVer, mid))
        {
            //다리가 갖는 최소 중량 Mid 값을 늘려야 한다는 말이다. (최대값에 도달하지 못했기때문)
            ans = mid;
            lo = mid + 1;
        }
        else
        {
            //다리가 갖는 최소 중량 Mid값을 줄여야 한다는 말이다.(최대값을 넘어섰기때문)
            hi = mid - 1;
        }
    }
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    
    input();
    binararySearch();
    cout << ans << "\n";
	return 0;
}

코드(java)

import java.util.*;

class Edge {
    int vertex, cost;
    Edge(int vertex, int cost) {
        this.vertex = vertex;
        this.cost = cost;
    }
}

public class Main {
    static ArrayList<Edge>[] a = new ArrayList[10001];
    static boolean[] visited = new boolean[10001];
    static int n, m, startVer, endVer;

    public static boolean go(int vertex, int mid) {
        if(visited[vertex])
            return false;
        
        if(vertex == endVer)
            return true;
        
        visited[vertex] = true;
        for(Edge e : a[vertex]) {
            int nextVer = e.vertex;
            int nextCost = e.cost;
            if(nextCost >= mid) {
                if(go(nextVer, mid))
                    return true;
            }
        }

        return false;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1; i <= n; i++) {
            a[i] = new ArrayList<Edge>();
        }
        
        for(int i = 0; i < m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int cost = sc.nextInt();
            a[from].add(new Edge(to, cost));
            a[to].add(new Edge(from, cost));
        }

        startVer = sc.nextInt();
        endVer = sc.nextInt();

        int lo = 1, hi = 1000000000, ans = 0;
        while(lo <= hi){
            Arrays.fill(visited, false);
            int mid = (lo + hi) / 2;
            if(go(startVer, mid)) {
                lo = mid + 1;
                ans = mid;
            } else {
                hi = mid - 1;
            }
        }
        System.out.println(ans);
    }
}