[Softeer](LV 3) 사물인식 최소 면적 산출 프로그램

문제 링크

LV 3: 사물인식 최소 면적 산출 프로그램

구현 방식

• N이 100이하, K가 20이하 정도여서 dfs를 통한 brute force로 풀어주었다

• dfs 함수를 구현할 때, 인자값으로 현재 노드에 minX, minY, maxX, maxY 값들을 저장해주어야한다

코드

import sys

N, K = map(int, sys.stdin.readline().split())

group = dict()
for n in range(N):
    x, y, k = map(int, sys.stdin.readline().split())
    if k in group: group[k].append((x, y))
    else: group[k] = [(x, y)]

def dfs(minX, minY, maxX, maxY, group_num, local_answer):
    global answer

    if group_num > K:
        answer = min(answer, local_answer)
        return

    for x, y in group[group_num]:
        nminX = min(x, minX)
        nminY = min(y, minY)
        nmaxX = max(x, maxX)
        nmaxY = max(y, maxY)
        tmp = (nmaxX-nminX)*(nmaxY-nminY)
        if tmp < answer:
            dfs(nminX, nminY, nmaxX, nmaxY, group_num+1, tmp)


answer = (2*10**3) * (2*10**3)
for x, y in group[1]:
    dfs(x, y, x, y, 1+1, (2*10**3) * (2*10**3))
print(answer)