[ 백준 22967 ] 구름다리 (c/c++)

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

 

 

[ 문제 요약 ]

학교의 지름은 한 건물에서 다른 건물로 가장 빠르게 이동할 때 최대 다리의 수를 말한다.

N-1개의 다리가 이미 설치되어 있는 학교에 최대 N-1개의 다리를 설치하여서 지름을 가장 적게하기 위해 설치해야 하는 다리와 지름, 다리를 설치할 다른 두 건물의 번호를 한 줄에 하나씩 출력한다.

 

 

[ 문제 풀이 ]

1. N * (N - 1) / 2 <= 2 * (N - 1)을 만족할 경우 모든 경로에 다리를 놓을 수 있기 때문에 학교의 지름은 1이 된다.

2. 위 식을 줄이면 N <= 4이 되므로 이 경에는 이미 다리가 놓이지 않은 모든 경로에 다리를 놓으면 된다.

3. 다른 경우에는 모든 건물을 한 건물과 연결시킬 경우에는 최대 2번만 거쳐서 갈 수 있으므로 지름은 2가 된다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N, R = 0;
int arr[303][303];
vector<pair<int, int>> v;

int main() {
    cin >> N;
    for (int i=1; i<N; i++){
        int a, b;
        cin >> a >> b;
        arr[a][b] = arr[b][a] = 1;
    }

    for (int i=1; i<=N; i++) arr[i][i] = 1;
    if (4 >= N){
        R = 1;
        for (int i=1; i<=N; i++){
            for (int j = i + 1; j<=N; j++){
                if (!arr[i][j]){
                    v.push_back({i, j});
                    arr[i][j] = arr[j][i] = 1;
                }
            }
        }
    }
    else {
        R = 2;
        for (int i=1; i<=N; i++){
            if (!arr[i][1]){
                arr[i][1] = arr[1][i] = 1;
                v.push_back({i, 1});
            }
        }
    }

    cout << v.size() << '\n' << R << '\n';
    for (int i=0; i<v.size(); i++) cout << v[i].first << " " << v[i].second << "\n";
        
    return 0;
}

 

 

 

[ 주의할 점 ]

지름이 1이 되는 경우, 지름이 2가 되는 경우를 잘 생각해보고 지름이 3이상이 되는 경우가 없을 알면 쉽게 풀 수 있다.