[SWEA] 4012_요리사 (DFS 이용)

📕 문제

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

SW Expert Academy

 

💡 풀이법

1. dfs의 n은 현재까지 고른 재료의 개수이고, k는 탐색해야할 리스트의 시작점이다.

2. 먼저 처음에는 n = 0 이고, k는 0부터 가능하기 때문에 dfs(0, 0)을 실행시킨다.

3. 만약 n이 N//2이 되면 반을 고른거기 때문에 멈추고, 현재까지 고른 재료는 A, 고르지 않은 재료는 B의 재료로 해서 시너지들의 합을 구한다. 두 시너지의 합의 차이와 ans를 비교해서 더 작은 것을 ans에 저장하고 return한다.

4. n이 N//2이 아니라면 k부터 N-1까지 for문을 돌면서 방문하지 않았다면 방문 체크를 하고 dfs(n+1, i+1) 을 실행시켜준다. (i를 골랐기 때문에 현재까지 고른 재료의 개수를 +1하고 그 다음부터는 i 다음부터 탐색해주기 위해 시작점을 +1해주는 것)

5. 그다음 다시 방문체크를 해제해야한다.

 

def synergy(lst):
    total = 0
    for i in range(len(lst)-1):
        for j in range(i+1, len(lst)):
            total += matrix[lst[i]][lst[j]] + matrix[lst[j]][lst[i]]
    return total

def dfs(n, k):
    global ans
    if n == N//2:
        A = []
        B = []
        for i in range(N):
            if visited[i]:
                A.append(i)
            else:
                B.append(i)
        total_A = synergy(A)
        total_B = synergy(B)
        ans = min(ans, abs(total_A - total_B))
        return

    for i in range(k, N):
        if not visited[i]:
            visited[i] = 1
            dfs(n+1, i+1)
            visited[i] = 0

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    matrix = [list(map(int, input().split())) for _ in range(N)]
    visited = [0 for _ in range(N)]
    ans = 999999
    dfs(0, 0)
    print('#{} {}'.format(tc, ans))