백준 1708번 문제(볼록 껍질) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

1708번: 볼록 껍질

 

정답 코드는 아래와 같습니다.

import sys
import math
 
class Point:
  def __init__(self, x, y):
    self.x = x
    self.y = y
 
  def __lt__(self, other):
    return self.x < other.x if self.x != other.x else self.y < other.y
 
  def __sub__(self, other):
    return Point(self.x - other.x, self.y - other.y)
 
  def incl(self, other):
    return math.inf if self.x == other.x else (self.y - other.y)/(self.x - other.x), self.x, self.y
 
  def cross(self, other):
    return self.x * other.y - self.y * other.x
 
def CCW(p, a, b):
  return (a-p).cross(b-p)
 
def convexHull(arr):
  p = min(arr)
  idx = arr.index(p)
  arr[0], arr[idx] = arr[idx], arr[0]
  arr = arr[:1] + sorted(arr[1:], key = lambda a: a.incl(p))
  hull = []
  for item in arr:
    while len(hull) >= 2 and CCW(hull[-2], hull[-1], item) <= 0:
      hull.pop()
    hull.append(item)
  return hull
 
def solve():
  n = int(sys.stdin.readline().rstrip())
  arr = []
  for _ in range(n):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    arr.append(Point(a, b))
  print(len(convexHull(arr)))
 
solve()
 

 

Convex hull 문제의 대표 예제입니다.

이 문제를 풀기위한 알고리즘은 다양한 연구자들이 개발하였으며, 저는 그 중에서 Graham scan 알고리즘을 이용하여 이 문제를 풀었습니다.

Grahan scan 알고리즘에 대한 증명은 다른 자료를 참고해주시기 바랍니다.

Grahan scan 알고리즘은 크게 점들을 정렬하는 단계와 정렬된 점들을 stack 에 넣거나 빼는 단계로 나눌 수 있습니다.

정렬하는 부분은 소스코드에서 28번째 line 이고, 넣어야 하는 stack 는 29번째 line 의 hull 이며, 그 아래의 for 문을 반복하며 조건에 따라 값을 담거나 담겨 있는 값을 제거합니다.

이 알고리즘에 대한 큰 흐름은 모두 설명드렸습니다.

이제 세부적으로 정렬은 어떻게 하는 것인지, stack 에는 어떤 조건에 따라 넣거나 빼는 것인지 등이 있겠습니다.

그러한 내용은 사실 다른 분들의 글에서도 아주 잘 설명되어 있으며, 제가 영상에서도 설명드렸기 때문에 추가로 여기서 언급하지 않겠습니다.(혹시 수학과 과학에서 사용하는 vector 를 모르신다면 이해하기 어려울테니, 먼저 수학과 과학에서 말하는 vector 가 무엇인지 이해하셔야 제 설명을 이해할 수 있을 것입니다.)

 

728x90

 

저는 이번 글에서 Graham scan 알고리즘 그 자체보다는 추상화의 의미와 그 중요성에 대하여 말하고 싶습니다.

세부적인 내용을 제외한다면 Graham scan 알고리즘은 "점을 정렬하고 조건에 따라 stack 에 데이터를 담거나 뺀다." 라고 간단하게 줄여서 말할 수 있습니다. 그리고 실제로 코드(convexHull 함수)도 그렇게 되어 있습니다.

그 다음에 해야할 것은 정렬하는 조건과 list에 넣거나 뺄 때 사용하는 조건을 코드로 작성하는 것입니다.

정렬하는 조건을 작성할 때에는 그 조건이 무엇인지가 중요한 것이지, Graham scan 에서 다른 것들이 바뀌면 지금 조건도 바뀌는 것은 아닙니다. 다시 말해서 Grahan scan과 무관(?)하게 코드를 작성할 수 있습니다.

지금 이 무관하다는 말이 잘 와 닿지 않을 수 있을테니 그럼 list에 넣거나 뺄 때 사용하는 조건에 대한 코드를 보겠습니다.

그 조건에에서 CCW 값을 사용하는데, CCW 에 대한 구현은 Graham scan 과 무관하다는 것입니다. CCW 코드 작성할 때에는 다 잊고, CCW 만 만들면 되는 것이라는 겁니다.

CCW를 구현할 때에도 3개의 점에 대하여 CCW 를 한다는 것은 결국 vector 의 외적을 하라는 것이니, 그냥 외적을 하고 그 값을 반환하는 것입니다.

외적하는 코드를 작성할 때에도 마찬가지입니다. 외적과 Graham scan 의 조건들은 상관이 없다는 것입니다. 외적하는 코드는 그냥 외적하는 코드입니다.

누군가에게 대뜸 외적하는 코드를 작성하라고 하면, 그 사람이 Graham scan 알고리즘을 고민하면서 외적하는 코드를 작성하지 않는다는 것입니다. 이게 제가 위에서 말했던 무관하다는 뜻입니다.

vector 의 뺄셈도 마찬가지로 Graham scan 알고리즘과 상관없이 그냥 vector 두 개에 대하여 뺄셈을 하면 되는 것입니다.

이런 식으로 전체 큰 그림을 잘게 나누고 그 중에 서로 영향받지 않는 부분들을 따로 분리하여 구현하는 것은 코딩을 할 때 매우 중요한 능력입니다.

추상화를 잘 하게 되면 다른 사람(또는 3개월 후의 나)도 코드를 이해하기가 좋습니다. 이런 것을 흔히 가독성이 좋다고 말합니다. 코드의 유지보수에도 도움이 됩니다.

단순히 PS 만을 위해서라면 추상화가 필요없다고 생각하는 사람들도 있지만, 막상 PS를 하면서 debugging 이 필요한 순간에는 각 기능별로 테스트하여 문제점을 더 빠르게 찾는 경우도 있습니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=k5eqrlPE3RI 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)