[백준/3392] 화성 지도 (Python)

Problem : https://www.acmicpc.net/problem/3392

3392번: 화성 지도

 

Difficulty : Platinum 2

 

Status : Solved

 

Time : 00:19:06

 

---

 

문제 설명

 

 

2051년, 야심차게 발사한 화성탐사선 성화가 탐사한 곳의 화성 지도를 N개 보냈다.

화성탐사선의 성공에 의기양양해진 BaSA(Baekjoon Space Agency)는 야심찬 계획을 발표했다.

화성 전체 지도를 만들겠습니다!

전체 지도를 만들기 전에, 지금까지 화성탐사선이 보낸 지도를 모두 합쳤다. 이때, 이 지도의 크기는 몇일까?

탐사선이 보낸 지도는 항상 직사각형 모양이며, 겹칠 수도 있다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000)으로 이루어져 있다. (x1, y1)와 (x2, y2)은 직사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표이다. 모든 지도는 직사각형이고, 변은 항상 x축과 y축에 평행하다.

 

출력

 

첫째 줄에 지금까지 탐사선이 보낸 지도를 모두 합쳤을 때, 그 면적을 출력한다. (직사각형을 모두 합쳤을 때 면적)

 

입력 예시

 

2
10 10 20 20
15 15 25 30

 

출력 예시

 

225

 

 

---

 

풀이

 

 

 

2차원이긴 하지만, 근본적으로는 라인 스위핑과 동일하다. 시작 지점의 선을 (y1, x1, x2-1)라고 두면, 끝점의 선 (y2, x1, x2=1)까지의 모든 영역을 더해주면 된다. 즉 시작 지점에는 +1하고, 끝 지점에는 -1을 하여 구간이 갱신될 때마다 이전 구간과 현재 구간 사이의 면적을 구하는 것이 팁이 되겠다. 이는 세그먼트 트리로 O(logN) 시간복잡도 체크할 수 있다.

 

하지만 단순히 세그먼트 트리를 사용한다면 중복을 제대로 체크하지 못한다. 위의 예시에서는 두 직사각형 사이의 중첩되는 구간의 넓이를 중복해서 카운트하게 될 것이다. 즉 우리는 트릭 사용하도록 한다. 세그먼트 트리 외에도 [start, end] 구간 정보를 추가적으로 저장하는 변수(cnt)를 사용하자.

 

• 만약 그 구간 전체를 업데이트하게 된다면 cnt값을 변동하면 된다.
• cnt값이 1 이상이라면, 현재 구간 전체를 덮는 직선이 하나 이상이란 뜻이다. 즉 tree[idx]값은 전체 구간 길이인 end - start + 1이 된다.
• 반대로 cnt값이 0이라면, 현재 구간 전체를 덮는 직선이 존재하지 않는다. 즉 기존 세그먼트 트리처럼 tree[idx]값은 자식 노드의 값의 합, 즉 tree[idx*2] + tree[idx*2+1]이 될 것이다.

 

 

풀이 코드

import sys
input = sys.stdin.readline

MAXLEN = 30001
tree = [0]*(4*MAXLEN)
cnt = [0]*(4*MAXLEN)

def update(start, end, idx, l, r, val) :
  if r < start or end < l :
    return
  if l <= start <= end <= r :
    cnt[idx] += val
  else :
    mid = (start + end) // 2
    update(start, mid, idx<<1, l, r, val)
    update(mid+1, end, idx<<1|1, l, r, val)
  if cnt[idx] > 0 :
    tree[idx] = end - start + 1
  else :
    tree[idx] = tree[idx<<1] + tree[idx<<1|1]

N = int(input())
coord = []
for _ in range(N) :
  x1, y1, x2, y2 = map(int, input().split())
  coord.append((y1, x1, x2-1, 1))
  coord.append((y2, x1, x2-1, -1))

coord.sort()
prev = coord[0][0]
ret = 0
for y, l, r, val in coord :
  if prev != y :
    ret += tree[1] * (y - prev)
    prev = y
  update(0, MAXLEN-1, 1, l, r, val)
print(ret)

풀이 완료!