M'S Blog

M'S Blog

WWDC20 student challenge Winner!

백준 1939 - 중량제한

최대 1 분 소요

문제

백준 1939 - 중량제한 풀러가기

문제 풀이

이 문제의 해결 포인트는 2가지가 있다.

  1. 출발 공장에서 도착 공장으로 갈 수 있는가? - 그래프 문제다.
  2. 옮길 수 있는 중량의 최대값은 얼마인가? - 탐색 문제다.

1의 경우에는 bfs, dfs를 이용하여 갈 수 있냐/없냐를 판단하면 된다.

그렇다면 2의 경우는?

가능한 중량이 10억까지 있으므로, 하나하나 탐색을 하면 분명 시간 초과가 걸릴 것이다.

그래서 이분 탐색을 통해 문제를 해결하고자 한다.

w라는 무게가 통과할 수 있다면, w보다 작은 무게는 무조건 통과할 수 있으므로 w의 무게를 올린다.

w라는 무게가 통과할 수 없다면, w보다 큰 무게는 무조건 통과할 수 없으므로 w의 무게를 낮춘다.

문제 코드(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    #include <cstdio>
    #include <vector>
    #include <cstring>
     
    using namespace std;
     
    vector<vector<pair<int, int>>> a(10001);
    bool visit[10001];
    int st, dt;
     
    bool go(int limit, int curr) {
     
        if (visit[curr]) {
            return false;
        }
        visit[curr] = true;
        if (curr == dt) {
            return true;
        }
        for (int i = 0; i < a[curr].size(); i++) {
            int next = a[curr][i].first;
            int weight = a[curr][i].second;
            if (weight >= limit) {
                if (go(limit, next)) {
                    return true;
                }
            }
        }
     
        return false;
    }
     
    int main() {
        int n, m;
     
        scanf("%d %d", &n, &m);
     
        for (int i = 0; i < m; i++) {
            int s, d, w;
            scanf("%d %d %d", &s, &d, &w);
            a[s].push_back(make_pair(d, w));
            a[d].push_back(make_pair(s, w));
        }
     
        scanf("%d %d", &st, &dt);
     
        int left = 1;
        int right = 1000000000;
        int mid;
        int ans = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            memset(visit, false, sizeof(visit));
            if (go(mid, st)) {
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
     
        printf("%d", ans);
     
        return 0;
    }
    		cs
    • 11~31번째 줄 : 일반적인 재귀를 이용한 dfs 코드에 중량을 체크하는 경우를 포함시킨다. 무조건 연결되어있다고 다음으로 갈 수 있는 것이 아니라, 중량 제한을 넘지 않아야 갈 수 있다.
    • 54번째 줄 : 현재 무게를 통해 도착 공장까지 갈 수 있는 경우다. 이 경우에 정답을 현재 무게로 바꿔주고, 현재 무게보다 더 큰 무게가 가능한지 확인을 위해 left의 값을 증가시킨다.
    • 59번째 줄 : 현재 무게를 통해 도착 공장까지 갈 수 없는 경우다. 이 경우에는 현재 무게를 낮춰야 하므로 right의 값을 감소시킨다.





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고