[BOJ / C++] 24164번 : 光ファイバー網の整備 (Fiber)

문제

クロアチアでは国内の全ての都市を光ファイバー網で結ぶ計画が進行している．光ファイバー を用いた通信回線は極めて高品質かつ高速であり，複数の都市を経由していても，ほとんど速 度が低下することなく，高速な通信を行うことができる．例えば，k 個の都市 A1, . . . , Ak に対 し，都市 Ai と Ai+1 (1 ≤ i ≤ k − 1) の間に光ファイバーが敷設されていれば，都市 A1 と Ak の 間で高速通信を行うことができる．

クロアチア政府は，国全体に光ファイバー網を張り巡らせて，全ての都市と都市の間で高速 通信が行えるようにしたいと考えている．ところが困ったことに，現在では，規制緩和の影響 で複数の光ファイバー敷設業者が乱立しており，国全体の光ファイバー網がどうなっているの か誰も把握していない．そこで，各業者から提出された光ファイバーの敷設情報を元に，全て の都市と都市の間の高速通信を可能にするためには，あと何本の光ファイバーを新たに敷設す る必要があるのかを調べることにした．

光ファイバーの敷設情報が与えられたときに，全ての都市と都市の間で高速通信を可能にす るために，あと何本の光ファイバーを新たに敷設する必要があるのかを求めるプログラムを作 成せよ．

입력

入力の1行目には，クロアチア国内の都市の個数n (1 ≤ n ≤ 10000) が書かれている．各都市には 1 から n までの番号が付けられている．2 行目には，敷設されて いる光ファイバーの本数を表す整数 m (1 ≤ m ≤ 30000) が書かれている．続く m 行 (3 行目 ～ m + 2 行目) は光ファイバーの敷設情報を表す．i + 2 行目 (1 ≤ i ≤ m) には 2 つの異なる整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) が空白を区切りとして書かれている．これは，都市 ai と都市 bi の間に光ファイバーが敷設されていることを意味する．

출력

出力は，標準出力に行うこと．全ての都市と都市の間で高速通信を可能にするため に新たに敷設が必要な光ファイバーの本数の最小値を出力せよ．もし，現在のままでも全ての 都市と都市の間で高速通信が可能な場合は，0 を出力せよ．

Solved.ac 레벨

실버 I

풀이

#include <bits/stdc++.h>
#define MAX 30001

using namespace std;

int n, m, ans;
vector<int> city[MAX];
bool visited[MAX];
queue<int> q;

void BFS(int start) {
    visited[start] = true;
    q.push(start);

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

        for(int i = 0; i < city[cur].size(); i++) {
            int next = city[cur][i];
            if(!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}


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

    cin >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        city[a].push_back(b);
        city[b].push_back(a);
    }

    for(int i = 1; i <= n; i++) {
        if(!visited[i]) {
            BFS(i);
            ans++;
        }
    }

    cout << ans - 1 << "\n";

    return 0;
}

생각보다 엄청 간단한 문제였다.

33개의 제출이 있었고 32개의 제출이 정답이었다. 나머지 1개는 내가 7달 전에 풀다가 틀려놓은 것이었다..... 아이고 부끄러워라 🤦🏻

 

N개의 정점이 있다면 이 정점들을 모두 연결할 수 있는 간선의 최소 개수는 N - 1개라는 사실을 알고만 있다면 정말 간단한 문제였다.

입력으로 주어지는 N개의 정점들은 M개의 간선으로 연결되어 있고, BFS 혹은 DFS를 통한 그래프 탐색을 통해 정점이 간선을 통해 연결되어 몇 개의 덩어리가 만들어지는지 알 수 있다. 그 덩어리들의 개수를 다시 정점의 개수로 생각해서 해당 정점들을 이을 수 있는 간선의 최소 개수를 구하면 된다.

 

문제 예제 입출력을 예로 들어보면 예제 입력으로 들어온 정점들과 간선들로 이어진 덩어리들은 BFS를 돌렸을 때 3개가 나온다.

따라서 모든 정점을 연결하기 위해 필요한 최소 간선은 3 - 1인 2가 된다.

24164번: 光ファイバー網の整備 (Fiber)