아직 계정이 없으신가요? 회원가입

Dev. Talk

사물인식 최소 면적 산출 프로그램 dfs 질문 고수님들...초보입니다

회원사진sa2da94
126 views2021-10-15 14:50

import sys
import math

input = lambda: sys.stdin.readline().rstrip("\n")
def dfs(color,count,check):
    global answer, area ,p1,p2
    if count == K:
        if area<answer:
            answer = area
            return

    if count==0:
        for i in range(1,K+1):
            for j in range(len(color[i])):
                p1 = color[i][j]
                count =1
                check[i]=1
                for q in range(i+1,K+1):
                    for w in range(len(color[q])):
                        p2 = color[q][w]
                        count+=1
                        check[q]=1
                        area = abs(p1[0]-p2[0])*abs(p1[1]-p2[1])
                        if area>answer:
                            continue
                        if count<K:
                            dfs(color,count,check)
                            count -=1
                            check[q] =0
                        else:
                            answer = min(answer,area)

                count -=1
                check[i]=0

    else:
        if 0 in check:
            for r in range(K+1):
                if check[r]==0:
                    flag = False
                    for tx,ty in color[r]:
                        if (p1[0]<=tx<=p2[0] or p2[0]<=tx<=p1[0]) and (p1[1]<=ty<=p2[1] or p2[1]<=ty<=p1[1]):
                                count+=1
                                check[r]=1
                                flag=True
                                dfs(color,count,check)
                                check[r]=0
                                count-=1

                    if flag ==False:
                        return


    return


if __name__ =='__main__':
    global K,answer
    N,K = map(int,input().split())
    color = [[] for _ in range(K+1)]
    max_x =0
    min_x =math.inf
    max_y = 0
    min_y = math.inf
    for i in range(N):
        x,y,c = map(int,input().split())
        max_x = max(max_x,x)
        min_x = min(min_x,x)
        max_y = max(max_y, y)
        min_y = min(min_y, y)
        color[c].append([x,y])
    # print(color)
    answer = (max_x-min_x) * (max_y-min_y)
    check = [0 for _ in range(K+1)]
    check[0]=1
    dfs(color,0,check)
    print(answer)


알고리즘 초보인데 위에 코드가 오답과 시간초과 투성이네요...


혹시 최소 면적 산출 프로그램 dfs로 푸신 분있으신가요..


아니면 코드를 어떻게 고쳐야 시간초과나 오답이 안나올까요..


고수님들의 도움이 필요합니다