[Baekjoon] 14889번 : 스타트와 링크 (Python, 백트래킹)

[Baekjoon] 14889번 : 스타트와 링크 (Python, 백트래킹)

 

목차

 

 

 

 

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

14889번: 스타트와 링크

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 -  코드 길이 646B

 

백트래킹으로 방문되는 index에 대하여 dfs 재귀를 처리하고 방문한 곳들이 한팀 그렇지 않은 곳이 한팀을 이뤄 그에 따른 차이가 최소가 되는 값을 찾는 문제이다.

 

 

def dfs(depth, idx):
    global n, res
    if depth == n//2:
        p1, p2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visit[i] and visit[j]:
                    p1 += s[i][j]
                elif not visit[i] and not visit[j]:
                    p2 += s[i][j]
        res = min(res, abs(p1-p2))
        return

    for i in range(idx, n):
        if not visit[i]:
            visit[i] = 1
            dfs(depth+1, i+1)
            visit[i] = 0

import sys
input = sys.stdin.readline

n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
visit = [0] * n
res = 1e3
dfs(0, 0)
print(res)