[백준/BOJ] - 14889번 python 풀이 - backtracking

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

14889번: 스타트와 링크

---

백트래킹 조합문제를 풀 땐 

 

1. 가지치기의 기준을 어떻게 할 것인가.

2. 조합은 순열과는 다르게 순서가 의미가 없으므로

재귀함수를 반복할 때 변수 뽑는 것을 어떻게 처리해 줄 것인가

이 정도가 중요하다.

 

아래 코드에선 depth 즉, 몇개를 뽑았는지의 지표 변수가 주어진 n의 절반 만큼 뽑았을 경우를 기준으로

가지치기를 해줬다.

뽑은 변수는 매번 방문처리를 해주었기에 2중 for문을 돌리며 각 for문의 변수인 i, j가 방문 처리를 됐는지를 기준으로 

total1에 시너지 점수 플러스 여부를 결정한다.

반대로 i, j  두 변수 모두 방문 처리가 안 됐다면 둘다 A팀이 아닌 B 팀이란 의미이므로 total2에 시너지 점수를 더한다.

그리고 기존 mini 값 기준으로 최소를 가리면 된다.

 

개인적으로 중요하다 생각하는 부분은 재귀함수의 매개변수와

재귀함수의 메인 부분에 있는 for문의 range 부분이다.

해당 부분을 잘 처리해야 순열이 아닌 조합 도출이 가능하다.

---

백트래킹을 활용한 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
visit = [False] * (n+1)
mini = sys.maxsize

def recur(depth,idx):
    global mini
    if depth == n//2: #가지치기
        total1,total2 = 0,0
        for i in range(n):
            for j in range(n):
                if visit[i] and visit[j]:
                    total1 += arr[i][j]
                elif not visit[i] and not visit[j]:
                    total2 += arr[i][j]

        mini = min(mini, abs(total1-total2))
        return
    
    for i in range(idx,n): #0부터 n-1까지 why? arr는 idx 0부터 시작되기 때문에 
        if not visit[i]:
            visit[i] = True
            recur(depth+1, i+1)
            visit[i] = False
     
recur(0,0)
print(mini)

 

itertool을 활용한 방법

 

#조합을 뽑고 나서 나머지 집합은 뽑히지않은 거로
#set 자료형에 - 연산을 사용한다면?
import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
mini = sys.maxsize
temp = set([])
for i in range(1,n+1):
    temp.add(i)

arr = [list(map(int,input().split())) for _ in range(n)]

for item in combinations(range(1,n+1),n//2):
    total1 = 0
    total2 = 0
    item_1 = list(set(item))
    item_2 = list(temp-set(item_1))    
    for r1 in combinations(item_1,2):
        total1 += arr[r1[0]-1][r1[1]-1]
        total1 += arr[r1[1]-1][r1[0]-1]

    for r2 in combinations(item_2,2):
        total2 += arr[r2[0]-1][r2[1]-1]
        total2 += arr[r2[1]-1][r2[0]-1]

    cal = abs(total1-total2)
    
    if  cal < mini:
        mini = cal

print(mini)

---

ref: https://hgk5722.tistory.com/319

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