BOJ 백준 3770번 대한민국

 

BOJ 백준 3770 대한민국

 

문제:www.acmicpc.net/problem/3770

3770번: 대한민국

​

대한민국의 동해안 도시와 서해안 도시가 각각 N개, M개 있고, 동해안과 서해안을 연결하는 고속도로가 K개 있을 때 고속도로가 서로 교차하는 곳의 개수를 구하는 문제이다. 단, 한 점에 교차하는 고속도로의 개수는 2개이다.

​

 

 

고속도로의 개수인 K의 제한이 40만이므로 시간 복잡도로 인해 단순히 loop를 두 번 시행함으로써 계산할 수 있는 문제는 아니다.

​

이 문제는 inversion count 유형에 속하며, 이러한 유형은 merge sort 알고리즘이나 segment tree 자료구조를 통해 풀 수 있다. 여기서는 segment tree 자료구조를 사용하여 해결했다. 이에 대한 자세한 설명은 counting inversion segment tree를 검색하면 된다. Segment tree를 사용한 풀이의 시간 복잡도는O(K * log(MAX(N, M))이므로 TLE를 받지 않는다.

​

 

 

tree 배열이 segment tree이고, tree 배열의 각 원소 값은 해당 노드가 가리키는 범위에 총 몇 개의 고속도로를 통해 동해안과 연결되어 있는지 그 합을 의미한다. Segment tree를 배열로 구현했으므로 현재 노드의 index가 x이고 이 노드가 가리키는 서해안 도시 번호 범위가 a ~ b일 때, 자식노드 두 개의 index는 각각 x * 2, x * 2 + 1이고 해당 자식 노드들이 가리키는 서해안 도시 번호 범위는 a ~ (a + b) / 2, (a + b) / 2 + 1 ~ b이다.

​

 

 

우선 고속도로를 동해안 도시 번호 크기 오름차순으로 정렬하고, 동해안 번호가 같으면 서해안 도시 번호 크기 오름차순으로 정렬한다. 정렬한 고속도로를 앞에서 차례로 보면서 해당 고속도로가 어떠한 서해안 도시 번호와 연결되었는지 확인한다. 이 때 확인한 서해안 도시 번호의 바로 뒷 번호에서 끝 번호까지의 범위가 총 몇 개의 고속도로를 통해 동해안과 연결되었는지 그 개수를 segment tree를 통해 구한다. 이를 수행하는 이유는 동해안 번호가 작은 고속도로부터 차례대로 보기 때문에 현재 서해안 도시 번호보다 뒷 번호에서 연결되는 고속도로가 존재하면 이는 현재 보고 있는 고속도로와 반드시 교점이 생길 수밖에 없기 때문이다. 이를 ans에 더하여 교차되는 구간의 개수를 추가하고, 현재 보고 있는 고속도로 상태를 segment tree에 갱신하기 위해 현재 서해안 도시 번호를 갖고 있는 범위의 segment tree 노드들의 값에 1을 더해준다. 위의 정리 노트에서 예제를 통해 이러한 과정을 설명하는 그림이 있다.

​

 

 

그러므로 sum segment tree를 구현해야 하고 segment tree의 값을 갱신하는 함수와 구간에 해당되는 값의 총합을 구하는 함수를 각각 만들어야 한다.

 

#include <cstdio>
#include <tuple>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int N_MAX = 1000;
long long tree[N_MAX * 4 + 1];
 
void update_tree(int start, int end, int node, int idx, long long diff){
    if (idx < start || end < idx){
        return;
    }
    tree[node] += diff;
    if (start != end){
        int mid = start + (end - start) / 2;
        update_tree(start, mid, node * 2, idx, diff);
        update_tree(mid + 1, end, node * 2 + 1, idx, diff);
    }
}
 
long long sum_query(int start, int end, int node, int left, int right){
    if (left > end || right < start) {
        return 0;
    }
     
    if (left <= start && end <= right){
        return tree[node];
    }
     
    int mid = start + (end - start) / 2;
    return sum_query(start, mid, node * 2, left, right) + sum_query(mid + 1, end, node * 2 + 1, left, right);
}
 
int main(){
    int t; scanf("%d", &t);
    for (int i = 1; i <= t; i++){
        memset(tree, 0, sizeof(tree));
         
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        vector<pair<int, int>> highway;
         
        for (int i = 0; i < k; i++){
            int x, y; scanf("%d %d", &x, &y);
            highway.push_back({x, y});
        }
         
        sort(highway.begin(), highway.end());
         
        long long ans = 0;
        for (int i = 0; i < k; i++){
            long long temp = sum_query(1, m, 1, highway[i].second + 1, m);
            ans += temp;
            update_tree(1, m, 1, highway[i].second, 1);
        }
        printf("Test case %d: %lld\n", i, ans);
    }
     
    return 0;
}