백준 10888번 두 섬간의 이동

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

10888번: 두 섬간의 이동

무려 열두 번 틀린 문제입니다. 그렇다고 어려운 문제는 아닙니다..

 

풀이 방법

임의의 A개의 섬이 A-1개의 다리를 통해 모두 연결되어 있다면,

이 A개의 섬에 대해 연결된 쌍의 개수와 최소 다리 개수의 합을 구할 수 있습니다.

 

1. 쌍의 개수

A×(A-1) / 2 = 쌍의 개수입니다. 

 

2. 최소 다리 개수의 합

섬 A개가 모두 연결되어 있을 때, 

다리 1개를 거쳐 연결되어 있는 쌍의 개수는 A-1개입니다.

다리 2개를 거쳐 연결되어 있는 쌍의 개수는 A-2개입니다.

...

다리 A-1개를 거쳐 연결되어 있는 쌍의 개수는 1개입니다. 

다리 A개를 거쳐 연결되어 있는 쌍은 없습니다.

즉 다리 개수의 합은 1×(A-1) + 2×(A-2) +...+ (A-2)×2 + (A-1)×1개입니다.

여기서 섬이 하나 추가되어 A+1개, 다리는 A개가 되었다면

다리 1개, 2개, ... A-2개, A-1, A개로 이루어진 쌍의 개수가 모두 하나씩 늘어납니다.

따라서 섬이 A개일 때 다리의 수가 S라면 섬이 A+1개일 때 다리의 수는 S+(1부터 A까지의 합)이 됩니다. 

A=2일때 다리의 개수를 알고 있으니 반복문을 통해 2 ≤ A ≤ N일때의 다리의 수를 미리 구할 수 있습니다.

 

이를 바탕으로 두 섬이 연결될 때마다 총 쌍의 수와 다리 개수를 적절히 바꿔 주면 답을 알 수 있습니다.

 

구현

쌍의 수와 다리 개수를 적절히 바꾸는 방법은 다음과 같습니다.

 

1. 두 섬이 연결될 때, 연결되기 전 두 섬과 연결되어 있는 섬의 개수를 각각 파악합니다.

2. 파악한 섬의 개수를 바탕으로 두 섬 그룹의 쌍의 개수와 다리 개수를 구합니다.

3. 현재 쌍의 수에서 두 섬 그룹의 쌍의 개수를, 현재 다리 개수에서 두 섬 그룹의 다리 개수를 뺍니다.

4. 두 그룹을 하나의 그룹으로 만든 뒤, 현재 쌍의 수와 총 다리 개수에 합쳐진 그룹의 쌍의 개수와 다리 개수를 더합니다.

 

이를 구현하기 위해 배열에 각 섬의 정보를 저장합니다.

각 섬의 정보는 연결된 섬의 갯수(cnt) 와 섬 그룹의 반대쪽 끝 섬(end) 을 나타내는 숫자입니다.

 

섬이 7개이고, 1-2번과 4-5-6-7번이 다리로 연결되어 있다고 가정하겠습니다. 

위 그림에서 나타내는 상황입니다. 

 

1, 2번 섬은 2개의 섬이 연결되어 있기 때문에 cnt는 2이며, end는 서로의 번호가 됩니다.

4, 7번 섬도 마찬가지로 그림처럼 cnt는 4, end는 각각 7, 4입니다.

5, 6번 섬은 다른 섬과 합쳐질 수 없기 때문에 cnt, end값이 필요없습니다.

 

현재 총 쌍의 개수는 (2개 섬의 쌍의 개수) + (4개 섬의 쌍의 개수) = 7개,

총 다리 개수는 11개입니다.

만약 여기서 2번 섬과 3번 섬을 합친다면 1번 섬의 cnt는 3, end는 3이 될 것이며,

3번 섬의 cnt는 1번처럼 3, end는 1이 될 것입니다. 

이후 3번 섬과 4번 섬을 합친다면 1번 섬의 cnt는 7, end는 7이 되고,

7번 섬의 cnt는 7, end는 1이 될 것입니다.

즉, 두 섬이 합쳐질 때 각 섬의 end번 섬에 대해 cnt = 두 섬의 cnt의 합, end = 상대 섬의 end가 됩니다.

이 과정을 반복할 때마다 공식을 통해 쌍의 개수와 다리 개수를 적절히 바꾸면 답을 찾게 됩니다.

 

코드

#include <cstdio>
#include <algorithm>
using namespace std;
 
struct island {
    long long int end;
    long long int cnt;
} map[100001]; // 섬들을 나타낸 구조체 배열
 
long long int cal(long long int n) {
    return n * (n - 1) / 2;
    // n개의 섬의 쌍의 수 공식, n-1까지의 합을 구하는 공식
}
 
long long int sum_list[100001]; // 다리 개수
 
int main() {
    int n, now;
    long long int pairs = 0, sum = 0, l, r, tmp;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        // 각 섬의 end, cnt 초기화
        map[i].end = (long long)i;
        map[i].cnt = 1LL;
        if (i > 1)
            sum_list[i] = sum_list[i - 1] + cal((long long)i); // 다리 개수 미리 구하기
    }
    
    for (int i = 1; i < n; i++) {
        scanf("%d", &now);
        l = map[now].cnt, r = map[now + 1].cnt;
        // 쌍의 수 적절히 바꾸기
        pairs -= cal(l);
        pairs -= cal(r);
        pairs += cal(l + r);
        // 다리 개수 적절히 바꾸기
        sum -= sum_list[l];
        sum -= sum_list[r];
        sum += sum_list[l + r];
        
        printf("%lld %lld\n", pairs, sum);
        // 합쳐졌을 때 cnt값 설정
        map[map[now].end].cnt = map[map[now + 1].end].cnt = l + r;
        // end값 설정
        tmp = map[now].end;
        map[map[now].end].end = map[now + 1].end;
        map[map[now + 1].end].end = tmp;
    }
    return 0;
}

 

섬에 end, cnt값을 담기 위해 섬들을 구조체 배열로 표현했습니다. 

다리 개수는 미리 구해 놓은 뒤 배열에서 찾아서 사용했고,

쌍의 수 공식과 1~A의 합 공식이 같아 함수를 만들어 사용했습니다.

 

사족

장황하게 썼는데, 이렇게까지 긴 글을 쓸 만한 문제는 아닌 것 같아요

분리 집합(Union-find)라는 걸 사용하면 쉽게 풀 수 있다고 해요

다음에 공부해 볼게요..

 

사실 풀이법은 첫 번째 제출하기 전부터 구상했는데

그럼에도 배열 범위 설정, 인덱스 오류 등 잡다한 실수를 많이 했어요