[Softeer] S531 사물 인식 최소 면적 구하기

[Softeer]

Question

Language: Python

해당 문제는 서로 다른 색깔 k개에 대해 모든 색깔에 대해 최소 한 개 이상의 좌표를 포함하는 최소 직사각형 면적을 구하는 것이 목표이다. 14568와 비슷한 유형의 문제이지만, 이번 문제의 경우 모든 색깔에 대한 고려를 해야한다는 점이다.

모든 좌표 점에 대해서 모든 가로, 세로 길이를 고려하는 것은 100*1000*1000 * 100(색깔에 대한 조사)로 시간 초과가 발생하게 된다.

그래서 해당 문제를 풀이하기 위해 각각의 색깔 별로 분리해서 각 색깔을 가지는 좌표점에 대해 직사각형의 면적을 갱신하는 방식으로 문제를 풀이할 수 있다.

def solution(color_index,left_row,left_col,right_row,right_col,area):
    global min_area
    if color_index==k:
        min_area=min(min_area,area)
        return

    for col,row in color_points[color_index]:
        temp_left_row=max(left_row,row)
        temp_left_col=min(left_col,col)
        temp_right_row=min(right_row,row)
        temp_right_col=max(right_col,col)
        
        temp_area=(temp_left_row-temp_right_row)*(temp_right_col-temp_left_col)
        if  temp_area < min_area:
            solution(color_index+1,temp_left_row,temp_left_col,temp_right_row,temp_right_col,temp_area)

Solution

import sys
from itertools import combinations
from math import inf

def solution(color_index,left_row,left_col,right_row,right_col,area):
    global min_area
    if color_index==k:
        min_area=min(min_area,area)
        return

    for col,row in color_points[color_index]:
        temp_left_row=max(left_row,row)
        temp_left_col=min(left_col,col)
        temp_right_row=min(right_row,row)
        temp_right_col=max(right_col,col)
        
        temp_area=(temp_left_row-temp_right_row)*(temp_right_col-temp_left_col)
        if  temp_area < min_area:
            solution(color_index+1,temp_left_row,temp_left_col,temp_right_row,temp_right_col,temp_area)
        
    
        
if __name__ == "__main__":
    n,k=map(int,sys.stdin.readline().split())
    points=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    min_area=2000**2
    color_points={i:[] for i in range(k)}
    for point in points:
        color_points[point[2]-1].append((point[0],point[1])) 

    solution(0,-1000,1000,1000,-1000,min_area)

    print(min_area)