[백준] 14889 파이썬(python) : 스타트와 링크 - (★)

14889번 : 스타트와 링크

 

 

백트래킹을 이용한 풀이)

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) ] #1
min_value = sys.maxsize #2

def backTracking(depth, idx): #3
    global min_value
    if depth == n // 2: #4
        power1, power2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visit[i] and visit[j]: #5
                    power1 += graph[i][j]
                elif not visit[i] and not visit[j]: #6
                    power2 += graph[i][j]
        min_value = min(min_value, abs(power1-power2)) #7
        return

    for i in range(idx, n): #8
        if not visit[i]:
            visit[i] = True
            backTracking(depth+1, i+1) #9
            visit[i] = False
backTracking(0, 0)
print(min_value)

 

 

#1 : 1차원으로 방문 리스트 생성

#2 : 최소값을 갱신할 변수 생성

#3 : 깊이를 나타내는 변수와 인덱스 변수를 인자로 받아줌

#4 : n은 늘 짝수로 주어진다고 했다. 주어진 수의 절반이 한 팀으로 선택되었을때 가지치기 시작

#5 : True의 값을 가지는 팀을 스타트팀이라 할때 스타트 팀의 능력치를 모두 power1에 더하고

#6 : 나머지 절반 False의 값을 가지는 팀을 링크팀이라 할때 링크 팀의 능력치를 모두 power2에 더한다.

#7 : 2중 for문이 끝났을때 그 둘의 차이의 절댓값이 변수보다 작으면 변수 갱신

#8 : #4의 조건에 걸리기 전(스타트 팀을 완성하지 못했을때) 백트래킹 실시

#9 : 깊이 +1, 같은 번호 중복을 막기위한 idx+1로 재귀호출

 

 

예제2번 예시

 

 

스타트팀과 링크팀을 두개의 변수가 아닌 visit과 not visit으로 나누는것과 일차원 리스트인 방문처리 리스트의 인덱스로 graph의 요소를 접근하는 발상이 대단하다.

 

 

조합을 이용해서 해결한 코드)

import sys
from itertools import combinations
n = int(sys.stdin.readline())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
members = list(range(n)) #1
min_value = sys.maxsize #2

for r1 in combinations(members, n//2): #3
    start, link = 0, 0
    r2 = list(set(members) - set(r1)) #4
    for r in combinations(r1, 2): #5
        start += graph[r[0]][r[1]]
        start += graph[r[1]][r[0]]
    for r in combinations(r2, 2): #6
        link += graph[r[0]][r[1]]
        link += graph[r[1]][r[0]]
    min_value = min(min_value, abs(start-link)) #7
print(min_value)

 

 

#1 : 전체 멤버를 포함하는 리스트 생성

#2 : 최소값을 비교할 변수 생성

#3 : 전체멤버의 절반을 r1으로 뽑아준다(스타트팀)

#4 : 나머지 절반은 r2로 차집합해서 빼준뒤 리스트화(링크팀)

#5 : 스타트팀에서 2명을 뽑아 팀의 능력치를 모두 더한다

#6 : 링크팀에서 2명을 뽑아 팀의 능력치를 모두 더한다

#7 : 한번의 r1으로 뽑는 조합이 끝날때마다 최소값 갱신

 

---

6603번 : 로또