[Python] 백준 12771 - Oil(석유왕)

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

문제

세계 경제는 유가에 많은 부분 의존한다. 그래서 석유를 발견하고 시추하는 새로운 방법이 여전히 연구되고 있다. 석유 기업의 이익은 얼마나 석유를 효율적으로 뽑아낼 수 있는지와 관련이 있다. 국제 석유 컨소시엄(ICPC)는 컴퓨터 시뮬레이션을 통해 석유를 어떻게 최선의 방법으로 뽑아낼 수 있는지 알아낼 수 있을 것으로 전망한다.

석유를 효율적으로 뽑아내는 것은 날마다 어려워진다. 새로이 발견된 석유 샘은 하나의 덩어리를 이루지 않고 종종 여러 굴로 나뉘어 있기 때문이다. ICPC는 현재 그림 G.1과 같이 층층이 구성된 석유 샘에 관심을 갖고 있다.

그림 G.1. 땅에 묻힌 석유층들. 그림은 예제 1에 대응된다.

분석을 간단히 하기 위해 ICPC는 2차원인 경우만 고려한다. 즉, 석유 샘은 지면과 평행한 가로선으로 모델링된다. ICPC는 정확히 하나의 굴을 파 최대한의 석유를 얻으려고 한다. 석유 굴은 하나의 직선을 이루고, 만나는 모든 석유 샘으로부터 석유를 뽑아낸다. 단, 선분의 끝점이 만나는 경우도 만나는 것으로 센다. 석유 샘 세 개와 만나는 석유 굴의 예를 그림 G.1에서 볼 수 있다. 이 모형에서 한 샘으로부터 뽑아내는 석유의 양은 샘의 길이와 같다. 굴을 하나 파서 뽑아낼 수 있는 석유의 최대 양은 얼마일까?

입력

첫째 줄에 석유 샘의 개수 n이 주어진다. (1 ≤ n ≤ 2 000) 다음 n개 줄 각각에는 샘의 정보를 나타내는 세 정수 x0, x1, y가 주어진다. (|x0|, |x1| ≤ 10^6; 1 ≤ y ≤ 10^6) 이는 샘이 (x0, y)과 (x1, y)를 양 끝점으로 하는 선분이라는 뜻이다. 모든 샘은 서로 교차하거나 끝점에서 만나지 않는다.

출력

굴을 하나 파서 뽑아낼 수 있는 석유의 최대 양을 출력한다.

 

---

 

풀이

간단한 아이디어 하나만 있으면 알고리즘은 꽤나 직관적이어서 그리 어렵지 않다. 다만 파이썬으로 구현이 조금 헷갈리고 어려울 뿐.

 

점의 개수가 2000개밖에 없으므로 우리는 다음의 $O(N^{2}log N)$ 풀이를 생각해볼 수 있다.

 

---

- 각 점에 대해서 다음을 반복한다.

1. 그 점을 pivot으로 잡고 나머지 2N - 1개의 점들을 각도순 정렬해준다. (같은 선분, 평행한 점들 제외)

2. 각도가 작은 순서대로 스위핑해준다.

3. 만약 각도가 같은데 여러개의 점들이 있는경우, 일단 해당 석유를 모두 뽑아준다. 그리고 스위핑에서 빼주던가 하자.

---

 

3번 경우는 다음과 같은 경우를 말하는 것이다.

빨간색 선을 보자. 2번 선분의 값을 스위핑하면서 빼주기 전에, 1번 선분을 먼저 더하고 최댓값을 갱신한 다음 2번 선분을 빼주어야 한다.

이를 쉽게 구현하려면 애초에 정렬 순서를 다음과 같이 해주면 될 것이다.

 

 

이를 쉽게 구현하기 위해 정렬을 할 때 튜플을 이용해서, atan2를 이용해서 각도를 우선순위로 정렬하되, atan2의 값이 같은 경우 se라는 값을 비교하도록 하였다.

se는 각 선분에서 이 선분이 오른쪽 끝점일때 0, 왼쪽 끝점일 때 1을 가지게 된다.

 

참고로, 이건 여담이지만 atan2는 여러분의 생각보다 매우매우매우 정확하다. 파이썬을 이용해서 각도 정렬할 일이 있다면 atan2를 애용해주도록 하자.

 

 

 

아 맞다, 아직 이 문제의 핵심 아이디어를 말하지 않았다!!

 

이 문제를 풀면서 꼭 구현해주어야 하는 핵심 아이디어는 바로, 어떤 점을 피벗으로 잡았을 때 피벗보다 밑에 있는 점은 피벗에 대해 점대칭을 시켜주어야 한다는 것이다.

 

그러면 탐색 범위가 360도에서 180도까지로 줄어들며, 정렬할 때 헷갈리지도 않는다.

 

 

아래의 나의 코드를 첨부한다. 본인은 각 선분들을 구별해주기 위해 각 선분에 code를 부여하였다. 맨 처음에 그냥 인덱스를 부여한거다.

뭐 구현 방법은 여러가지가 있겠지만 일단 위의 아이디어를 그냥 그대로 구현하면 웬만하면 된다.

 

import sys
from math import *
input = sys.stdin.readline
N = int(input())
dots = []
value = [0]*N
for i in range(N):
    x0, x1, y = map(int, input().split())
    x0, x1 = min(x0, x1), max(x0, x1)
    if x0 == x1:
        continue
    dots.append((x0, y, i, 0))
    dots.append((x1, y, i, 1))
    value[i] = x1 - x0
#print(value)
finalfinalans = 0
for i in range(len(dots)): #각 점들에 대해서
    pivotx, pivoty, pivotcode, se = dots[i]
    #print(dots[i])
    tmp = []
    for j in dots:
        if pivotcode == j[2]:
            continue
        if pivoty == j[1]:
            continue
        x, y, code, se = j
        if y < pivoty:
            x = pivotx + pivotx - x
            y = pivoty + pivoty - y
        tmp.append((x, y, code, se))
    tmp.sort(key = lambda x: (atan2(x[1] - pivoty, x[0] - pivotx), x[3]))
    #print(tmp)
    final = value[pivotcode]
    #여기서부터 스위핑 코드
    ans = value[pivotcode]
    visited = [False]*N
    visited[pivotcode] = True
    #print('초기값', ans)

    for nowx, nowy, nowcode, se in tmp:
        if not visited[nowcode]:
            ans += value[nowcode]
            visited[nowcode] = True
            final = max(final, ans)
            #print('더해줌', ans)
        else:
            ans -= value[nowcode]
            visited[nowcode] = False
            #print('빼줌', ans)
    #print(final)
    finalfinalans = max(finalfinalans, final)
print(finalfinalans)

2트컷