[Softeer 인증평가2차 기출]사물인식 최소 면적 산출 프로그램(파이썬)

https://softeer.ai/practice/info.do?idx=1&eid=531&sw_prbl_sbms_sn=169594 

Softeer

문제접근

 

1. 모든 케이스를 구해야한다

-->점들을 포함하는 경우가 각각이 다르기 때문에

모든 케이스를 구해서 그 중 최소를 받아준다.

그럴러면 부르드포스를 써야한다.

 

2. 각 점을 차례대로 받아준다

-->각 색마다 최소 하나씩이면 되기 때문에

각 점당 하나씩 받아주고 

그렇게 해서 만든 사각형 넓이 중 최소를 넘기면 된다.

dfs&백트레킹을 활용해서 모든 경우를 다 구해보자

 

 

함정 피하기

1. answer에 모든 경우를 다 가정하고 append하는 건 어떨까?

-->이 방식대로 한다면, 모든 케이스를 다 받아주고, sort해준 다음 맨 앞의 값(최소값)을 받아주면 된다.

그럴때는 최소한 answer에 나올 수 있는 최댓값을 넣어줘야한다.

그렇지 않다면 런타임에러가 발생할 수도 있다.

 

2. 시간초과를 어떻게 방지할까?

-->초반에 answer를 나올 수 있는 최댓값으로 설정하고

점을 계속 이으면서 만드는 사각형이

answer보다 작은지 계속 살펴본다.

현재 사각형이 answer보다 크다면 굳이 탐색을 더 할 필요가 없다.

(실제로 이걸 안해주면 시간초과가 뜬다)

 

코드

import sys

sys.setrecursionlimit(10 ** 8)

# -1000~1000까지 이므로 최대 넓이가 4*10^6입니다.
answer = 4 * (10 ** 6)


def dfs(num, K, minX, minY, maxX, maxY, color):
    global answer
    # 모든 색을 다 포함했다면 답과 비교해줍니다
    if num > K:

        X = abs(maxX - minX)
        Y = abs(maxY - minY)
        now = X * Y
        if answer > now:
            answer = now
        return
    # 사실 K개의 색이 모두 있으므로 굳이 if를 표시 안해도 되지만, 꼼꼼하게 할려면 이게 맞을듯합니다.
    if color[num]:
        for nx, ny in color[num]:

            NminX = min(minX, nx)
            NmaxX = max(maxX, nx)
            NminY = min(minY, ny)
            NmaxY = max(maxY, ny)
            tx = NmaxX - NminX
            ty = NmaxY - NminY
            temp = tx * ty
            # 현재까지의 넓이가 answer보다 작으면 dfs를 돌려줍니다
            # 굳이 지금 answer보다 큰 데 굳이 더 돌려주면서 시간초과 나는 것보다는 나으니깐.
            if answer > temp:
                dfs(num + 1, K, NminX, NminY, NmaxX, NmaxY, color)


N, K = map(int, input().split())
color = [[] for _ in range(K + 1)]

for _ in range(N):
    x, y, k = map(int, input().split())
    color[k].append((x, y))

# 1번색 좌표 각각마다 dfs시작점으로 잡아줌
for x, y in color[1]:
    dfs(2, K, x, y, x, y, color)

print(answer)

 

배워갈 것

시간초과 방지하기, 런타임에러 방지하기