[BOJ/Platinum 5] 백준 3770 대한민국(C++)

문제 링크

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

3770번: 대한민국

 

문제

대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다.

대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다)

고속도로가 서로 교차하는 곳에는 휴게소를 지으려고 한다. 한 점에서 교차하는 고속도로는 최대 2개이다. 고속도로가 주어졌을 때, 고속도로가 교차하는 곳의 개수를 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, M, K가 주어진다. K는 고속도로의 수이다. 둘째 줄부터 K개의 줄에는 고속도로의 정보가 주어진다. 고속도로의 정보는 숫자 2개로 이루어져 있다. 첫 번째 숫자는 동해안에 있는 도시의 번호이고, 두 번째 숫자는 서해안에 있는 도시의 번호이다.

고속도로의 개수는 40만개보다 작거나 같으며, 문제의 정답이 263-1보다 작거나 같은 경우만 입력으로 주어진다.

출력

각 테스트 케이스에 대해서, 교차점의 수를 케이스 번호와 함께 출력한다.

예제 입력 1

1
3 4 4
1 4
2 3
3 2
3 1

예제 출력 1

Test case 1: 5

알고리즘 분류

• 자료 구조

풀이

동해안의 도시 N을 Index, 서해안의 도시 M을 Value라고 한다면 이 문제는 Inversion Counting에 해당된다는 것을 알 수 있다.

따라서, 동해안의 도시 N과 연결되는 서해안의 도시 M들을 Vec[N] 벡터에 담고, 1번 동해안의 도시부터 해당 도시와 연결된 서해안의 도시 번호의 뒷 번호부터 M번까지의 서해안의 도시가 총 몇 개의 도로를 통하여 해당 동해안의 도시와 연결되었는지 세그먼트 트리를 이용하여 구한다. 이렇게 수행하는 이유는 현재 보고 있는 서해안의 도시보다 뒷 번호에서 연결된 고속도로가 존재하면 현재 도로와 교차할 수밖에 없기 때문이다.

도로의 개수를 구하면 총합에 더하고, 현재 도로의 정보를 세그먼트 트리에 추가한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int T, N, M, K;
vector<int> Vec[MAX];
vector<int> SegTree;
LL answer;

void Init() {
	for (int i = 0; i < MAX; i++) {
		Vec[i].clear();
	}
	SegTree.clear();
	answer = 0;
	int Height = (int)ceil(log2(N));
	int Size = (1 << (Height + 1));
	SegTree.resize(Size);
}

void Update_Tree(int Node, int Start, int End, int Val) {
	if (Start == End) {
		SegTree[Node] += 1;
		return;
	}
	int Mid = (Start + End) / 2;
	if (Val <= Mid) {
		Update_Tree(Node * 2, Start, Mid, Val);
	}
	else {
		Update_Tree(Node * 2 + 1, Mid + 1, End, Val);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

LL Query(int Node, int Start, int End, int Left, int Right) {
	if ((End < Left) || (Right < Start)) {
		return 0;
	}
	if ((Left <= Start) && (End <= Right)) {
		return SegTree[Node];
	}
	int Mid = (Start + End) / 2;
	return Query(Node * 2, Start, Mid, Left, Right) + Query(Node * 2 + 1, Mid + 1, End, Left, Right);
}

void Find_Answer(int Testcase) {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < Vec[i].size(); j++) {
			int X = Vec[i][j];
			answer += Query(1, 1, M, X + 1, M);
		}
		for (int j = 0; j < Vec[i].size(); j++) {
			int X = Vec[i][j];
			Update_Tree(1, 1, M, X);
		}
	}
	cout << "Test case " << Testcase << ": " << answer << "\n";
}

void Input() {
	cin >> T;
	for (int i = 1; i <= T; i++) {
		cin >> N >> M >> K;
		Init();
		for (int i = 0; i < K; i++) {
			int I, J;
			cin >> I >> J;
			Vec[I].push_back(J);
		}
		Find_Answer(i);
	};
}

int main() {
	FASTIO
	Input();

	return 0;
}