[SWEA] 4012. 요리사 (Python)

link 🔗 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH 

SW Expert Academy

 

 

def cal(lst):
    temp = 0
    for i in range(len(lst)-1):
        for j in range(i+1, len(lst)):
            temp += arr[lst[i]][lst[j]]
            temp += arr[lst[j]][lst[i]]
    return temp

def dfs(level, num):
    global Min
    if level == (N//2)-1:
        A = []
        B = []
        for idx in range(N):
            if check[idx] == 1:
                A.append(idx)
            else:
                B.append(idx)
        Min = min(Min, abs(cal(A)-cal(B)))
        return
    check[num] = 1
    for number in range(num+1, N):
        if check[number] != 1:
            check[number] = 1
            dfs(level+1, number)
            check[number] = 0

t = int(input())
for tc in range(1, t+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    check = [0 for _ in range(N)]
    Min = 2e18
    dfs(0, 0) # level, num
    print(f'#{tc} {Min}')

 

💥 주의

• 체크 배열을 [0 for _ in range(N)]으로 만들었어야 했는데 [x for x in range(N)]으로 해놓고 한참 디버깅 했다... 황당🙃