[SWEA] 8744 도로 제거

출처: SWEA

Approach

N개의 도시를 서로 한번씩 연결하면 (N × (N-1)) ÷ 2 의 간선이 생긴다.

ex) N = 4 → (4 × 3) ÷ 2 = 6

 

<문제 조건 中 일부>

"어떤 k개의 도로 폐쇄해도 서로 다른 두 도시간에 이동할 수 있음이 유지되도록 하고 싶다"

위 문제 조건을 이해한다면 어렵지 않게 구현할 수 있는 문제이다.

 

위 모습은 2(= M) 개의 간선을 제거한 상태이다.

(각 도시에 남아있는 도로 개수는 {빨간 숫자}로 표시)

 

"이동될 수 있음"을 보장하면서 도로를 추가로 제거한다면

도로 {② ↔ ④} 1(=k)개를 제거하거나 도로 {① ↔ ④}를 1(=k)개를 제거할 수 있다.

 

하지만 어떤 k개의 도로를 폐쇄해도 서로 다른 두 도시로 이동되어야 하기 때문에

제거되는 1개 도로가 {③ ↔ ④}가 된다면 ③번 도시로는 더이상 이동될 수 없다.

 

그렇기에 M개 도로가 제거되고, 연결된 도로가 가장 적은 도시를 탐색한다.

그리고 해당 도시의 {연결된 도로 - 1}이 문제에서 요구하는 해답이 된다.

---

#include <stdio.h>

inline int min(int A, int B) { return A < B ? A : B; }
const int MAX_NM = 1e4 + 2;
int TC, N, M, ans, from, to;
int edgeCnt[MAX_NM];

void init()
{
    ans = MAX_NM;
}

void input()
{
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++)
    {
        // 자기 자신을 제외한 다른 도시와 연결 도로 개수
        edgeCnt[i] = N - 1;
    }
    // 제거되는 M개 도로
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d", &from, &to);
        edgeCnt[from]--;
        edgeCnt[to]--;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; ++tc) {
        init();
        input();
        
        // 도시들 중에서 가장 적게 도로가 연결된 도시 탐색
        for (int i = 1; i <= N; i++) {
            ans = min(ans, edgeCnt[i]);
        }
        // 최대 찾은 도시의 연결된 {도로 개수-1} 제거 가능
        printf("#%d %d\n", tc, ans - 1);
    }
    return 0;
}