옛날에 휴리스틱이란 단어 자체가 되게 어려워보였고 기피하게 됐는데
지금 다시 접하니깐 정말 쉽고 간단한 방법인 듯 하다.

휴리스틱과 최소 외접원의 입문 문제를 하나 풀어보자.

BOJ 2389 - 세상의 중심에서...
(2022.10.25 기준 P1)
(치팅하면 세상의 중심에서 질타 받음)

문제

N명은 각 좌표 (x, y)에 있다. N명을 모두 포함하는 가장 작은 원의 가운데에서 공연을 하려고 할 때, 가운데의 좌표와 원의 반지름 출력

알고리즘

모든 점을 포함하는 가장 작은 원은 최소 외접원이다. 이는 휴리스틱으로 구하면 된다.

풀이

휴리스틱은 어림짐작하는 방법이다.
최소 외접원의 중심을 구해야 하므로 먼저 점들의 중간점을 잡는다.
그리고 중간점과 가장 멀리 떨어진 점을 찾고 조금씩 위치를 가장 멀리 떨어진 점과 가깝게 보정해주는 식을 반복해가면 된다. 이 때, 가깝게 해주는 비율을 점점 낮춰야 한다.

어려워 보이지만 어떻게 보면 이분 탐색과 같은 느낌으로 점점 정답과 가까워지는 간단한 방법이다.

그리고 최소 외접원은 무조건 볼록 껍질과 접한다. 그러므로 볼록 껍질을 구한 다음에 볼록 껍질의 점들로 휴리스틱을 돌리는 것이 시간 최적화하는 방법이라고 할 수 있다.

아주 간단하고 베이직한 휴리스틱 문제라서 코드를 보면 바로 이해가 갈 것이다.

코드

import sys; input = sys.stdin.readline

def ccw(a, b, c): # a-b-c가 반시계 방향인지 검사
    if (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0]) > 0:
        return True
    return False

def dist(a, b): # a-b 거리 계산
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

def solve():
    N = int(input())
    points = sorted(list(map(float, input().split())) for _ in range(N)) # 오름차순 정렬

    # monotone chain
    # 볼록 껍질의 아래
    down = []
    for i in range(N):
        while len(down) > 1:
            if ccw(down[-2], down[-1], points[i]):
                break
            down.pop()
        down.append(points[i])

    # 볼록 껍질의 위
    up = []
    for i in range(N - 1, -1, -1):
        while len(up) > 1:
            if ccw(up[-2], up[-1], points[i]):
                break
            up.pop()
        up.append(points[i])

    # 위와 아래를 합쳐 볼록 껍질을 만들자.
    hull = down[:-1] + up[:-1]
    size = len(hull) # 볼록 껍질의 꼭짓점 개수

    # 중간점 구하기
    ax = ay = 0
    for x, y in hull:
        ax += x
        ay += y
    ax /= size
    ay /= size

    # 휴리스틱
    rat = 0.1 # 보정 비율
    for _ in range(5000):
        D = I = -1 # 가장 멀리 떨어진 점과의 거리 및 그 점의 인덱스
        for i in range(size):
            d = dist([ax, ay], hull[i])
            if D < d:
                D = d
                I = i

        # 가장 멀리 떨어진 점과 조금 더 가깝도록 보정
        ax += (hull[I][0] - ax) * rat
        ay += (hull[I][1] - ay) * rat
        rat *= 0.995 # 보정 비율을 줄여나간다.

    print(ax, ay, max(dist([ax, ay], hull[i]) for i in range(size)))

solve()

여담

이러다가 기하학의 정점을 찍는게 아닌가 몰라.. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
생각보다 기하학 재밌다구..