백준 17490번 [일감호에 다리 놓기](C++) -yes6686- 티스토리

백준 문제 풀이: 17490 [일감호에 다리 놓기]

---

문제 링크: https://www.acmicpc.net/problem/17490

문제 설명:

일감호에는 총 N개의 섬이 원형으로 배치되어 있습니다. 일부 섬 사이에는 이미 다리가 설치되어 있고, 다른 다리는 비용이 주어졌습니다. 주어진 예산 K 안에서 모든 섬을 연결하는 것이 가능한지 판단하는 문제입니다.

즉, 최소 스패닝 트리를 구성하여 그 비용이 예산 K를 초과하지 않는지 확인하면 됩니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 간선을 저장할 벡터
vector<pair<int, pair<int, int>>> edges;
int connected[1000001]; // 특정 섬 사이 다리가 이미 설치되어 있는지 체크
int parent[1000001]; // 유니온 파인드 부모 배열

// 부모 노드를 찾는 함수 (경로 압축)
int getParent(int n) {
    if (parent[n] == n) return n;
    return parent[n] = getParent(parent[n]);
}

// 두 노드를 연결하는 함수
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

// 두 노드가 같은 집합에 속해 있는지 확인하는 함수
bool findParent(int a, int b) {
    return getParent(a) == getParent(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    long long k;
    cin >> n >> m >> k;

    // 다리가 하나 이하라면 무조건 연결 가능
    if (m <= 1) {
        cout << "YES\n";
        return 0;
    }

    // 유니온 파인드 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 각 섬의 비용 입력
    for (int i = 0; i < n; i++) {
        int cost;
        cin >> cost;
        edges.push_back({cost, {i + 1, n + 1}}); // 섬과 가상의 노드 연결
    }

    // 이미 연결된 다리 정보
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        if (a == 1 && b == n) {
            connected[b] = 1; // n과 1 사이 다리 체크
        } else {
            connected[a] = 1; // 다른 다리 체크
        }
    }

    // 연결되지 않은 인접 섬들 간의 가상의 간선 추가
    for (int i = 1; i <= n; i++) {
        if (connected[i] == 0) {
            if (i == n) {
                edges.push_back({0, {1, n}});
            } else {
                edges.push_back({0, {i, i + 1}});
            }
        }
    }

    // 간선들을 가중치 기준으로 정렬
    sort(edges.begin(), edges.end());

    long long totalMinWeight = 0; // 최소 스패닝 트리의 총 비용

    // 크루스칼 알고리즘
    for (int i = 0; i < edges.size(); i++) {
        int weight = edges[i].first;
        int u = edges[i].second.first;
        int v = edges[i].second.second;
        if (!findParent(u, v)) {
            unionParent(u, v);
            totalMinWeight += weight;
        }
    }

    // 최소 스패닝 트리의 비용이 예산을 초과하는지 확인
    if (totalMinWeight > k) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }

    return 0;
}

예제 입력:

5 2 10
1 2 3 4 5
1 2
4 5

예제 출력:

YES

---

코드 설명

• 핵심 알고리즘: 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 구성하고, 그 비용이 예산 K 이내인지 확인합니다.
• 구현 세부사항:
  • 각 섬과 가상의 노드(중앙 노드)를 간선으로 연결하여 MST를 구성합니다.
  • 간선의 가중치를 기준으로 정렬한 후, 사이클을 방지하면서 간선을 추가합니다.
  • 이미 연결된 다리는 체크 배열로 관리하여 중복 연결을 방지합니다.
• 시간 복잡도:
  • 간선 정렬: O(E log E), E는 간선의 개수
  • 유니온 파인드: O(α(V)), V는 정점의 개수
  • 전체 시간 복잡도: O(E log E)

---

결과

입력된 섬과 다리를 통해 최소 스패닝 트리를 구성한 뒤, 예산 내에서 모든 섬을 연결할 수 있는지 정확히 판단합니다. 크루스칼 알고리즘과 유니온 파인드를 활용한 문제 해결 연습에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!