BOJ 백준 11012 Egg
문제 : https://www.acmicpc.net/problem/11012
[ 문제 요약 ]
- 각 테스트케이스마다 2차원 좌표 평면 위에 여러 개의 점이 주어집니다. 이후 두 개의 좌표로 표현된 직사각형이 주어지며, 각 테스트케이스마다 해당 직사각형 내부(경계 포함)에 있는 점들의 개수를 구해 출력하는 문제입니다. 두 좌표는 직사각형의 서로 대각선 꼭짓점에 해당하며, 이 범위 안에 있는 모든 점의 개수를 세면 됩니다.
[ 테스트 케이스 설명 ]
1 // 테스트케이스 수(1<=20)
3 1 // 좌표의수N(0<=10,000), 쿼리수M(0<=50,000)
3 5 // N개의 줄에 x,y 각 좌표가 주어짐 각수는 0<=10의5승
2 3
1 1
1 2 1 3 // M개의 줄에 l, r, b, t가 주어짐 (0<=10의5승), l과r은 x좌표, b,t는 y좌표
답 : 2
[ 문제 풀이 ]
이 문제를 풀기 전에, 직사각형 안에 있는 점의 개수를 어떻게 빠르게 찾아 더 할 것인지를 먼저 알아야 합니다.
방법은, 좌표 평면에서 점의 위치를 특정한 형태로 만들어 놓고, 간단한 수학적인 계산으로 빠르게 구할 수 있습니다.
아래 표는 2차원 좌표평면을 표현한 것이고, 0은 점이 없는 것, 1은 점이 있는 위치를 나타냅니다.
세로는 Y좌표를, 가로는 X좌표를 나타냅니다.
| Y좌표 : 3 | 0 | 0 | 1 | 0 | 1 | 0 |
| Y좌표 : 2 | 0 | 1 | 1 | 0 | 0 | 0 |
| Y좌표 : 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| Y좌표 : 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| X좌표 : 0 | X좌표 : 1 | X좌표 : 2 | X좌표 : 3 | X좌표 : 4 | X좌표 : 5 |
위 와 같이 있다고 했을 때, 위 표를 아래 표와 같은 형태로 전환해서 만들면,
사각형의 두 꼭짓점을 알았을 때 쉽게 사각형 안에 있는 점 개수의 총합을 구할 수 있습니다.
글로 먼저 설명하자면, x좌표 하나하나마다 y좌표가 낮은 곳에서 높은 곳으로 올라가면서 누적합을 구하면 됩니다.
| Y좌표 : 3 | 0 | 2 ↑ | 2 ↑ | 1 ↑ | 1 | 1 ↑ |
| Y좌표 : 2 | 0 | 2 ↑ | 1 ↑ | 1 ↑ | 0 | 1 ↑ |
| Y좌표 : 1 | 0 | 1 ↑ | 0 ↑ | 1 ↑ | 0 | 1 ↑ |
| Y좌표 : 0 | 0 | 0 ↑ | 0 ↑ | 0 ↑ | 0 | 0 |
| X좌표 : 0 | X좌표 : 1 | X좌표 : 2 | X좌표 : 3 | X좌표 : 4 | X좌표 : 5 |
위 와 같이 X좌표마다 Y좌표를 작은 수에서 큰 수로 올라가면서 누적합을 구합니다.
위와 같은 표가 준비되었을 때, 예를 들어 구하려는 사각형의 두 꼭짓점이 (y=3, x=1) / (y=1, x=3)이라 하면,
Y좌표는 3과 1입니다. 먼저 Y가 3일 때를 구합니다. X의 범위는 1~3까지가 되니 Y=3, X=1~3 범위의 모든 숫자를 더합니다.
그러면 2+2+1 = 5입니다. Y가 3일 때는 구했으니 Y가 1일 때의 합도 구합니다.
그런데 Y 값이 낮은 행은 Y 값에서 1을 추가로 빼야 합니다.
그럼 Y가 0이면서, X가 1~3 사이의 값을 모두 더합니다. Y좌표가 0인 경우는 X의 값이 모두 0이므로 합해도 0입니다.
그럼 Y=3일 때 구한 5와 Y=0일 때 구한 0을 빼면 5가 나오는데, 이 5가 해당 사각형 안에 있는 점의 개수입니다.
위와 같이, 좌표 평면에서 Y를 낮은 좌표에서 높은 좌표순으로 올라가면서 누적합을 구해놓고,
Y좌표에 따른 X좌표 사이의 값들의 합을 구해서 빼주기만 하면 됩니다.
이것을 빠르게 구현하기 위해 영속성 세그먼트 트리(PST)를 사용합니다.
영속성 세그먼트 트리의 기본 내용과 구현 방법은 아래 글을 참고해 주세요!
영속성 세그먼트 트리 : https://kyjdummy.tistory.com/5
Persistent Segment Tree(PST) - 영속성 세그먼트 트리
[ 글을 쓰게 된 계기 ]- PST(Persistent Segment Tree) 알고리즘을 공부하면서 느낀 점은, 개념에 대한 대략적인 설명은 많지만, 원리나 코드 적용 방법, 구현 과정에서의 인사이트를 초보자가 쉽게 이해
kyjdummy.tistory.com
영속성 세그먼트 트리를 구현할 때, 루트 노드(roots)는 Y좌표입니다. Y좌표 기준으로 X좌표를 업데이트해나갑니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class Point implements Comparable<Point>{
int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
@Override
public int compareTo(Point o) {
return y - o.y;
}
}
class Node{
int left, right, sum;
Node(int l, int r, int s){
left=l;
right=r;
sum=s;
}
}
class Main{
static final int LEN = 100_001;
static ArrayList<Node> nodes;
public static int init(int s, int e) {
if(s == e) // 리프노드인 경우 노드를 추가하고 해당 노드 번호를 반환하고 종료
{
nodes.add(new Node(-1, -1, 0));
return nodes.size() - 1;
}
// 리프노드가 아닌 경우 왼쪽 오른쪽을 탐색하며 노드를 만들어나간다.
int mid = (s + e) >> 1;
int l = init(s, mid);
int r = init(mid + 1, e);
nodes.add(new Node(l, r, 0));
// 최종적으로 자기자신의 노드번호(size - 1)를 반환
return nodes.size() - 1;
}
public static int update(int nowNode, int s, int e, int targetIdx) {
Node now = nodes.get(nowNode);
if(s == e)// 리프노드인 경우, 기존 sum에서 + 1을 하여 x좌표에 대해 입력된 횟수를 1더함
{
nodes.add(new Node(-1, -1, now.sum + 1));
return nodes.size() - 1;
}
// 리프노드가 아닌 경우, targetIdx의 값, 즉, 목표로하는 x좌표의 값에 따라 왼쪽으로갈지, 오른쪽으로 갈지 정하여 탐색
int mid = (s + e) >> 1;
int l = now.left;
int r = now.right;
if(targetIdx <= mid) {
l = update(now.left, s, mid, targetIdx);
}
else {
r = update(now.right, mid + 1, e, targetIdx);
}
// 왼쪽, 혹은 오른쪽 자식이 갱신되었을 텐데, 그 갱신된 값을 통해 노드를 새롭게 생성한다. 이 때 x좌표에 대해 입력된 횟수 + 1을함
nodes.add(new Node(l,r, now.sum + 1));
// 갱신된 노드번호(size - 1)반환
return nodes.size() - 1;
}
public static int sum(int nowNode, int s, int e, int left, int right) {
if(e < left || right < s)
return 0;
if(left<=s && e<=right)
return nodes.get(nowNode).sum;
int mid = (s + e) >> 1;
return sum(nodes.get(nowNode).left, s, mid, left, right)
+ sum(nodes.get(nowNode).right, mid + 1, e, left, right);
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());//테스트케이스 수(1<=20)
while(T-->0)
{
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());// 좌표수
int M = Integer.parseInt(st.nextToken());// 쿼리수
Point point[] = new Point[N];
int roots[] = new int[LEN + 1];
nodes = new ArrayList<>();
for(int i=0; i<N; i++)
{
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()) + 1;// 좌표의수N(0<=10,000)
int y = Integer.parseInt(st.nextToken()) + 1;// 쿼리수M(0<=50,000)
point[i]= new Point(x,y);
}
// 초기 세그먼트 트리 생성, roots[0]에는 초기 세그먼트트리의 root번호, 즉 nodes의 사이즈가 들어간다.
roots[0] = init(1, LEN);
Arrays.sort(point);
int prevY = 0;
for(Point p : point)
{
for(int y=prevY; y<=p.y; y++)
{
// 이전 탐색한 y좌표 부터 현재 파악하려는 p.y좌표까지 복사를 진행한다.
// 이로써 쿼리에서 어떤 y좌표가 입력되어도 그 때의 세그먼트트리 루트노드를 찾아갈 수 있다.
roots[y] = roots[prevY];
}
// 복사된 루트노드(root[p.y])를 시작으로 x의 인덱스를 마킹하고 새로운 루트 노드를 재저장한다.
// p.y가 같은 값이 여러개 입력되어도, 결국 roots[p.y]에는 마지막으로 x좌표를 업데이트한 루트노드번호만 저장됨
roots[p.y] = update(roots[p.y], 1, LEN, p.x);
prevY = p.y;
}
// 남은 y좌표를 끝까지 update한다.
for(int y=prevY; y<=LEN; y++)
roots[y] = roots[prevY];
int result = 0;
while(M-->0)
{
st = new StringTokenizer(br.readLine());
// l, r, b, t가 주어짐 (0<=10의5승), l과r은 x좌표, b,t는 y좌표
int l = Integer.parseInt(st.nextToken()) + 1;
int r = Integer.parseInt(st.nextToken()) + 1;
int b = Integer.parseInt(st.nextToken()) + 1;
int t = Integer.parseInt(st.nextToken()) + 1;
result += sum(roots[t], 1, LEN, l, r)
- sum(roots[b - 1], 1, LEN, l, r);
}
sb.append(result)
.append('\n');
}
System.out.print(sb);
}
}
[ 코드 해석 ]
- 좌표 입력 시 +1을 하는 이유 : roots 배열은 y좌표 기준으로 생성되는데, PST를 처음 init 할 때, y좌표 0에 루트 노드 값을 담기 때문에 y좌표가 0인 경우가 필요합니다. 입력되는 y좌표의 범위가 0 ~ 100,000이기 때문에 +1을 하여 입력되는 y좌표를 최소 1부터 시작되도록 보정한 것입니다.
- roots 배열을 복사해나가는 이유 : 코드에서 roots[y] = roots[prevY] 부분이 있는데, 이건 모든 y좌표에 대해서 PST의 루트 노드를 저장시켜야 하기 때문입니다. 주어지는 점의 좌표와, 구하고자 하는 사각형의 꼭짓점 좌표가 일치하지 않을 수 있기 때문에 모든 y 점에 대해서 루트 노드를 저장시켜야 합니다. 복잡해 보이지만 결국 y좌표 기준으로 x좌표를 업데이트한 최종 PST만 쓰이게 됩니다.