[백준 - Python] 14889. 스타트와 링크 (완전 탐색)

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

 

코드

from itertools import combinations
import sys
input= sys.stdin.readline

n = int(input())
st = [list(map(int, input().split())) for _ in range(n)]
p = [i for i in range(1, n+1)]

total = 0
for i in range(n):
    total += sum(st[i])

def teamSt(l):
    per = list(combinations(l, 2))
    tmp = 0
    for pp in per:
        a, b = pp
        if a == b:
            continue
        team1 = st[a-1][b-1] + st[b-1][a-1]
        tmp += team1
    return tmp


result = []
per = list(combinations(p, n//2))  # 가능한 팀 조합
for p in per:
    l = list(p)
    ll = [i for i in range(1, n+1) if i not in l]
    team1 = teamSt(l)
    team2 = teamSt(ll)
    result.append(abs(team2-team1))

print(min(result))

 

가능한 팀 조합을 구하고

해당 조합으로 팀을 구성했을 때,

각 팀 별 능력치를 조합을 이용해서 각각 구한 후

차이를 구해서 구한 차이들의 최솟값을 구하는 방식으로 문제를 풀었다.

 

시간이 오래 걸리긴 했지만 통과는 됐다.

 

itertools의 순열, 조합 함수들 중,

사용해야 하는 함수가 무엇인 지를

중복 가능 여부를 잘 생각하고 선택해야 한다.

 

리스트 컴프리헨션 사용 시에 조건을 걸을 때,

for문 다음에 if 조건을 걸어주어야 하고,

if 조건을 여러 개 걸어줄 수 있다.

 

 

백트래킹 풀이

import sys
n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visit = [False for _ in range(n)]
min_value = sys.maxsize

def backTracking(depth, idx):
    global min_value
    if depth == n // 2:     # n은 늘 짝수 / 주어진 수의 절반이 한 팀으로 선택 되었을 때, 가지치기 시작
        power1, power2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visit[i] and visit[j]:   # True 값을 가지는 팀의 능력치 power1에 합산
                    power1 += graph[i][j]
                elif not visit[i] and not visit[j]:     # False 값을 가지는 팀의 능력치 power2에 합산
                    power2 += graph[i][j]

        min_value = min(min_value, abs(power1-power2))  # 능력치 차이가 이미 저장된 변수보다 작으면 갱신
        return

    for i in range(idx, n):
        if not visit[i]:
            visit[i] = True
            backTracking(depth+1, i+1)      # 같은 번호 중복을 막기 위한 idx+1 인덱스로 재귀 호출
            visit[i] = False


backTracking(0, 0)
print(min_value)

 

항상 백트래킹 풀이가 최선은 아닐 수 있다!