[python] algospot MINASTRITH 문제 풀이

문제

최소의 인원으로 성벽의 모든 부분을 감시하기 위해, 일부 초소에만 병사를 배치하려고 합니다. 각 초소의 위치와 감시 범위가 주어질 때, 성벽의 모든 부분을 감시하기 위해 필요한 최소한의 병사 수를 계산하는 프로그램을 작성하세요.

문제를 간단하게 하기 위해 성벽은 두께가 없는 원이고 초소는 점이라고 가정합니다

-> 문제 링크 : https://www.algospot.com/judge/problem/read/MINASTIRITH

algospot.com :: MINASTIRITH

 

문제풀이

문제에서 입력값으로는 초소의 좌표값과 반지름이 주어진다.

하지만 이 좌표 만으로는 초소가 감시하는 영역을 찾고 다른 초소와 비교하기 힘들다.

그렇기에 좌표값을 다른 값으로 바꿔주어야 한다.

우리는 공식을 통해 두 원이 접할 때 의 호 길이와 각도를 계산할 수 있다.

호의 길이는 영역의 범위는 나타낼 수 있지만 여러개의 호 길이를 비교하며 원을 덮었는지 계산하기는 쉽지 않다.

범위를 나타낼 수 있고, 비교 연산이 가능한 방법은 각도를 사용하는 것이다.

 

각도는 3시방향을 시작으로 0~360도로 나타낸다. 초소의 감시 영역을 두 원의 접점에서의 각도로 나타낸다.

 

모든 초소를 범위로 나타내면  360을 넘거나 0보다 아래인 수가 나타난다.

문제가 직선 상의 범위가 아닌 원 위에서의 범위이기 때문에 끝에 도달하면 처음부터 다시 시작하게 된다.

이 범위가 원 위에 있다는 점이 문제를 어렵게 만드는 요소이다. 

모두 신경써서 문제를 풀려고 한다면 문제가 너무 복잡해진다.

 

그렇기에 우리는 원을 직선으로 펴서 문제를 간단하게 만들 것이다.

그러면 우리가 덮어야할 범위는 0 ~ 360이 된다. 

이 때 우리는 무조건 0 or 360 을 지나는 직선을 포함해야 한다.

그렇기에 문제를 0 or 360을 지나는 직선 A를 포함하면서 0 ~ 360 범위를 모두 덮을 수 있는 선분의 최소 수로 정하겠다.

 

직선 A를 먼저 선택하고 나면 커버해야 할 범위인 0 ~ 360은 a ~ b로 변하게 된다.

그럼 직선 상에서 범위를 갖는 선분을 이용해 a ~ b 영역을 모두 덮는 최소 수를 구하면 된다.

 

만약 현재까지 커버한 영역이 covered_a, covered_b 라면 ( 초기 값은 둘 다 a가 될 것이다. )

이를 위한 식은 간단한데 선분의 리스트를 오름차순으로 정렬하고

선분이 작은거부터 선택한다. 반복문을 통해 선분의 시작값이 covered_b보다 작은 것들을 모두 구하고 

선분의 끝 값을 모두 저장한다. 그리고 그 중에서 가장 큰 값을 골라 covered_b로 지정한다. 

이를 반복하다보면 직선상에 있는 선분을 최소 선분 개수로 커버하게 된다.

 

코드

import sys
from math import atan2, pi, degrees, asin

# 1개
T = int(sys.stdin.readline().rstrip())

def convertToAngle(y,x,r) :

    degree = degrees(atan2(y,x))
    degree = degree if degree >0 else degree + 360
    cover = 2*degrees(asin(r/16))
    return degree-cover, degree+cover

def solve( lines ) :

    def solve_line(S, M) :

        covered_s = S
        covered_m = S
        idx = 0
        cnt = 0

        while idx < len(lines) :
            maxEnd = 0
            while idx < len(lines) and lines[idx][0] <= covered_m :
                maxEnd = max(maxEnd, lines[idx][1])
                idx += 1
            covered_m = maxEnd
            cnt += 1

            if covered_m >= M and covered_s <= S :
                return cnt

        # while문을 다 돌렸는데 S ~ M이 커버가 안된다면 실패
        return -10000000

    lines = sorted(lines, key = lambda x: (x[0], x[1]))
    cnt = float('inf')

    for idx, line in enumerate(lines) :

        start = line[0]
        end = line[1]

        if start <= 0 or end >= 360:

            if start <=0 :
                range_end = 360+start
                range_start = end

            else :
                range_end = start
                range_start = end-360

            cnt = min(cnt, solve_line(range_start, range_end) + 1 )
    return cnt

for _ in range(T) :
    N = int(sys.stdin.readline().rstrip())
    R = 8
    check_points = []

    for _ in range(N) :
        y, x, r = map(float, sys.stdin.readline().rstrip().split(" "))
        check_points.append(convertToAngle(y,x,r))

    ans = solve(check_points)

    if ans < 0 :
        print("IMPOSSIBLE")
    else :
        print(ans)

 

초기 접근 방식과 오답의 원인

algospot에서는 시간 초과가 난다.

왜그런지 모르겠다.

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.