[BOJ] 백준 1615번 교차개수세기 (Java)

#1615 교차개수세기

난이도 : 플레 5

유형 : 세그먼트 트리 / 펜윅 트리

1615번: 교차개수세기

▸ 문제

각각 N(1 ≤ N ≤ 2,000)개의 쌍으로 이루어진 2N개의 정점과 M(1 ≤ M ≤ N×(N-1)/2)개의 간선으로 구성된 이분그래프가 주어질 때 서로 교차하는 총 개수를 구하는 것이다.

• 교차 조건 : 한 독립 집합 A와 다른 독립 집합 B가 연결된 두 개의 간선을 (A1, B1), (A2, B2)라 한다면 A1 < A2, B1 > B2 또는 A1 > A2, B1 < B2를 만족한다면 두 간선을 교차한다고 한다.

예를 들어 위에 예에서 (3, 2)는 (1, 5)와 (5, 1)과 교차한다. 이 문제를 해결하는 프로그램을 작성하시오.

▸ 입력

첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. 중복되는 간선이 입력으로 주어지지 않는다.

▸ 출력

입력에서 주어진 간선이 교차하는 총 개수를 출력한다.

 

문제 풀이  

Inversion counting 문제로 해당 풀이는 9%에서 메모리초과가 나지만 맞는 풀이입니다. 문제 메모리 제한이 128MB이기 때문에 자바 코드로는 통과할 수 없습니다. 같은 유형 문제로 백준 7578번 문제가 있으니 이 문제를 푸는 것을 추천드립니다. 이 문제는 메모리 제한이 256MB이라 가볍게 풀이가 가능합니다.

 

Inversion counting 

n+1의 크기를 가진 tree 배열을 만들고 tree[x]는 [1, x]까지 연결된 선분의 수를 나타낸다. 그리고 arr[i]는 i가 연결된 위치라고 할때, i를 인덱스로 반복문을 돌리면서 arr[i]값을 통해 답을 도출해낼 수 있다.

1. 먼저 i-sum(arr[i])를 반전 쌍의 갯수에 더해준다. (이미 연결된 선의 개수 - 자신과 겹치지 않는 선 개수)로 보면된다.
2. update(arr[i]) tree의 arr[i]에 해당하는 인덱스에 +1을 더해준다. [1, arr[i]]까지 연결된 수를 효율적으로 카운팅해준다.

 

(i, j)가 있을 때, i를 오름차순으로 정렬하고 j에 대해서 자신보다 앞에 선이 몇 개 있는지 카운트해주면 된다. 

 

1. x =1, (i =0, arr[i] =5)

• (1-5)의 선과 교차되는 선은 없으므로 0-0 = 0 이다.
• 1번을 반대편 정점 5번과 연결시킨다.

 

2. x =2, (i =1, arr[i]=2)

• (2-2)의 선보다 먼저 연결된 선은 1개, 교차되지 않는 선은 0개이므로 교차되는 선은 1-0 = 1개이다.
• 2번을 반대편 정점 2번과 연결시킨다.

 

3. x =3, ( i =2, arr[i]=2)

• (3-2)보다 이전에 연결된 선은 2개, 교차되지 않는 선은 2개이므로 둘다 교차된다. 따라서 2개가 카운트된다.
• 3번을 반대편 정점 2번과 연결시킨다.

 

4. x =4, (i=3, arr[i]=3)

• (4-3)보다 이전에 연결된 선은 3개, 교차되지 않는 선은 2개(sum(3))이므로 3-2 = 1개가 교차된다.
• 4번을 반대편 정점 3번과 연결시킨다.

이런 식으로 펜윅트리를 사용하여 풀이를 해주면 된다.

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	
	static int n;
	static int[] tree;
	static void update(int idx, int val) {
		while(idx <= n) {
			tree[idx] += val;
			idx += idx & -idx;
		}
	}
	
	static long sum(int idx) {
		long res =0;
		while(idx > 0) {
			res += tree[idx];
			idx -= idx & -idx;
		}
		return res;
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
	
		tree = new int[n+1];
		Map<Integer, List<Integer>> map = new HashMap<>();
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			map.computeIfAbsent(a, list -> new ArrayList<>()).add(b);
		}
		
		List<Integer> keyList = new ArrayList<>(map.keySet());
		Collections.sort(keyList);
		
		int idx=0;
		long res = 0;
		for(int key : keyList) {
			for(int num : map.get(key)) {
				res += (idx++)-sum(num);
				update(num, 1);
			}
		}
		System.out.println(res);
	}
}