[BOJ] 17490 - 일감호에 다리 놓기

https://www.acmicpc.net/problem/17490

BOJ - 일감호에 다리 놓기

문제 유형: 분리 집합, 그래프, 그리디

문제 난이도: Gold III

시간 제한: 2초

메모리 제한: 256MB

 

문제

학교의 홍보대사를 맡게 된 건덕이는 건국대학교의 모든 강의동을 신입생들에게 소개해야 한다.

건국대학교 중앙에 위치한 일감호를 따라 한 바퀴를 돌며 모든 강의동을 소개하는 것이 그의 일이지만, 몇몇 구간들이 공사 중이어서 그 구간을 통해서는 갈 수 없는 상황이다. 급한대로 건덕이는 호수에 돌을 던져 징검다리를 놓아 길을 만들어보려고 한다.

강의동은 일감호의 둘레에 따라 원형으로 배치돼 있으며, 강의동 양 옆의 강의동은 서로 이웃한다. 또, 원형으로 배치돼 있기 때문에 N개의 강의동이 있다면 N번째 강의동과 1번째 강의동은 서로 이웃한다.

일감호 안에는 와우도라는 섬이 있다. 건덕이는 한 강의실에서 다른 모든 강의실로 이동할 수 있도록 강의동에서 와우도까지 징검다리를 놓기로 했다. 하지만 건덕이의 눈에는 K개의 돌밖에 보이지 않는다. 건덕이는 주어진 돌을 활용해서 징검다리를 완성할 수 있을까?

 

입력

첫째 줄에 강의동의 수 N, 공사구간의 수 M, 건덕이가 가진 돌의 수 K가 공백으로 구분돼 주어진다. 강의동은 1동부터 N동까지 존재한다.

다음 줄에는 강의동에서 와우도까지 놓아야하는 돌의 개수 S1, S2, ..., SN이 공백으로 구분돼 주어진다. 이는 T번째 강의동에서 와우도까지 ST개의 돌을 놓아야 함을 의미한다. 이어서 M개의 줄에 i, j가 주어진다. 이는 i번째 강의동에서 j번째 강의동까지 가는 길이 공사중임을 의미한다. 이 때 입력되는 i, j번째 건물은 이웃한 강의동이다. 공사중인 구역은 한 번만 주어진다.

 

출력

건덕이가 가지고 있는 돌을 놓아 모든 강의동을 연결할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

 

풀이

강의동들간에 연결 컴포넌트를 구성한다. 그러고 각 연결 컴포넌트별로 와우도까지의 최소 비용을 가진 노드를 그 연결 컴포넌트의 루트로 지정한다.

 

연결컴포넌트가 하나라면 당연히 YES가 된다.

그렇지 않다면, 각 연결컴포넌트의 루트별로 와우도까지의 최소 비용들을 누적한다.

그 값이 k이하라면 YES, 그렇지 않다면 NO이다.

 

 

코드

C++

#include <bits/stdc++.h>

#define ll long long
using namespace std;

int n, m;
ll k;

int getRoot(int x, vector<int>& parent) {
    if (parent[x] == x) return x;
    return parent[x] = getRoot(parent[x], parent);
}

void merge(int x, int y, vector<int>& build_cost, vector<int>& parent) {
    int rootX = getRoot(x, parent);
    int rootY = getRoot(y, parent);

    if (rootX == rootY) return;

    if (build_cost[rootX] < build_cost[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootX] = rootY;
    }
}

void expand(int node, vector<int>& build_cost, vector<bool>& left_banned,
            vector<bool>& right_banned, vector<int>& parent,
            vector<bool>& visited) {
    queue<int> q;
    q.push(node);
    visited[node] = true;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        if (!left_banned[curr]) {
            int left = (curr - 1 + n) % n;
            if (!visited[left]) {
                merge(left, node, build_cost, parent);
                q.push(left);
                visited[left] = true;
            }
        }

        if (!right_banned[curr]) {
            int right = (curr + 1 + n) % n;
            if (!visited[right]) {
                merge(right, node, build_cost, parent);
                q.push(right);
                visited[right] = true;
            }
        }
    }
}

int main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;

    vector<int> build_cost(n, 0);
    vector<bool> left_banned(n, false);
    vector<bool> right_banned(n, false);
    vector<int> parent(n, 0);
    iota(parent.begin(), parent.end(), 0);
    vector<bool> visited(n, false);

    for (int i = 0; i < n; i++) {
        cin >> build_cost[i];
    }

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        if (u > v) swap(u, v);

        if (u == 0 && v == n - 1) {
            left_banned[u] = true;
            right_banned[v] = true;
        } else {
            right_banned[u] = true;
            left_banned[v] = true;
        }
    }

    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        expand(i, build_cost, left_banned, right_banned, parent, visited);
    }

    ll sum = 0;
    int component_count = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] == i) {
            sum += build_cost[i];
            compoenet_count++;
        }
    }

    if (component_count == 1) {
        cout << "YES\n";
        return 0;
    }
    if (sum <= k) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}