[백준] 14889번, 스타트와 링크 (Python)

문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

코드

n = int(input())
graph = [list(map(int, input().split(" "))) for _ in range(n)]
curMin = 10000000
check = [False] * n


def recursive(index, count1, count2, sum1, sum2):
    global curMin
    if index == n:
        if count1 == count2:
            curMin = min(curMin, abs(sum1 - sum2))
        return
    
    check[index] = True
    temp = 0
    for i in range(index):
        if check[i] == True:
            temp += graph[i][index] + graph[index][i]
    recursive(index+1, count1+1, count2, sum1+temp, sum2)

    check[index] = False
    temp = 0
    for i in range(index):
        if check[i] == False:
            temp += graph[i][index] + graph[index][i]
    recursive(index+1, count1, count2+1, sum1, sum2+temp)

recursive(0, 0, 0, 0, 0)
print(curMin)

범위가 작아서 완전탐색 재귀풀이로 문제를 풀어보았다.

 

check[index]가 True일 경우 스타트팀, False일 경우 링크팀으로 계산한다.

for문을 돌아 if문 조건에 맞으면 같은팀 이므로 temp에 값을 저장하고 다시 재귀를 돌아준다.

 

탈출조건으로는 index가 n이랑 같아지면 더 깊은 재귀가 없으므로 return을 해주고 만약 count1, count2 둘이 같으면 curMin에 더 작은 값을 넣어준다.

 

ex)

true : 1, 2
false : 0
현재 인덱스 3으로 true이면 1,3 3,1 2,3 3,2에 값이 temp에 들어가고

기존 sum에 있는 값(1,2 2,1)에 더해줘서 스타트팀 1,2,3에 값이 sum1에 누적된다