124. 14889(스타트와 링크)

import sys
input = sys.stdin.readline

N = int(input())
visited = [False] * N
startLink = [list(map(int,input().split())) for _ in range(N)]
result = []

def teamCalc():
    startTeam = 0
    LinkTeam = 0
    
    for i in range(N):
        for j in range(i+1,N):
            if visited[i] and visited[j]:
                startTeam += startLink[i][j]
                startTeam += startLink[j][i]
            elif not visited[i] and not visited[j]:
                LinkTeam += startLink[i][j]
                LinkTeam += startLink[j][i]      
    result.append(abs(startTeam - LinkTeam))

def DFS(start, depth):
    if depth == N // 2 :
        teamCalc()
        return
    
    for i in range(start, N):
        if not visited[i]:
            visited[i] = True
            DFS(i, depth+1)
            visited[i] = False
  
DFS(0,0)
print(min(result))

문제요약

스타트 팀과 링크 팀의 전력차가 최소값이 되도록 하시오.

설명

먼저 두 가지를 생각한다.

1. 함수 하나를 이용해서 깊이우선 탐색으로 스타트 팀을 구한다.

2. 다른 함수 하나를 이용해서 구한 값을 가지고 링크팀과 스타트팀 합을 구한다.

 

 

1. 함수 하나를 이용해서 깊이우선 탐색으로 스타트 팀을 구한다.

def DFS(start, depth):
    if depth == N // 2 :
        teamCalc()
        return
    
    for i in range(start, N):
        if not visited[i]:
            visited[i] = True
            DFS(i, depth+1)
            visited[i] = False

재귀함수의 종료 조건은 N//2 이다. 

N//2인 이유는 스타트팀 혹은 링크팀 중 한 팀만 구하면 되기 때문에 2로 나눈 것이다.

 

for문은 예를 들어 보겠다.

 

N = 4라고 할 경우

다음 과 같이 구해지며 편의상 0과 1만 구했다. (뒤에 2, 3도 나오게됨.)

 

 

2. 다른 함수 하나를 이용해서 구한 값을 가지고 링크팀과 스타트팀 합을 구한다.

def teamCalc():
    startTeam = 0
    LinkTeam = 0
    
    for i in range(N):
        for j in range(i+1,N):
            if visited[i] and visited[j]:
                startTeam += startLink[i][j]
                startTeam += startLink[j][i]
            elif not visited[i] and not visited[j]:
                LinkTeam += startLink[i][j]
                LinkTeam += startLink[j][i]      
    result.append(abs(startTeam - LinkTeam))

1번의 재귀가 끝나고 Calc로 들어왔다.

visited가 True라는 것은 탐색을 했다는 것이고, ij가 모두 탐색된 경우에는 start 팀이다.

반대로 ij가 모두 탐색되지 않은 경우는 link 팀이다.

 

이 둘의 값을 빼주고 절대값을 붙여주어 결과 리스트에 넣어 주었다.