[백트랙킹] 14889번 스타트와 링크

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 40 + a

1. 문제 설명

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

14889번: 스타트와 링크

2. 접근 방식

- 해당 문제는 재귀를 활용해서 문제를 한 번 풀고, 조합을 이용해서 문제를 한 번 풀었다.

- 재귀적 문제풀이

1) team1에 들어갈 수 있는 번호를 재귀를 통해 집어넣는다.

2) team1에 멤버의 절반이 들어간다면, team1에 들어가지 않은 멤버들을 가지고 team2를 만든다.  

3) team1과 team2의 멤버들을 활용해서 입력으로 주어진 그래프에서 값을 계산해서 difference를 구한다.

4) 해당 과정을 끝까지 반복함으로 difference의 최소값을 프린트한다.

 

- 조합을 활용한 문제풀이

1) 가능한 멤버의 조합을 combinations를 활용해 구한다.

2) combinations함수의 특성을 이용해서, (n이 총 멤버의 수라고 할 때, i < n//2) 

 2-1) team1 = combinations[i]  

 2-2) team2 = combinations[-i]

3) 위에서 만든 team1, team2의 값을 빼서 difference을 구한다.

4) 모든 조합에 대해 2~3 과정을 진행하고 difference를 프린트한다. 

3. 코드

- 재귀를 활용한  문제풀이

def check_team(team1, team2):
    sum_1 = 0
    sum_2 = 0
    for i in range(n//2):
        for j in range(n//2):
            sum_1 += cond[team1[i]][team1[j]]
            sum_2 += cond[team2[i]][team2[j]]
    return abs(sum_1-sum_2)

def make_team(team1, count, start):
    global answer, n
    if count == n // 2:
        team2 = []
        for i in range(n):
            if i not in team1:
                team2.append(i)
        diff = check_team(team1, team2)
        answer = min(diff, answer)
        return
    
    for i in range(start, n):
        if i not in team1:
            team1.append(i)
            make_team(team1, count+1, i+1)
            team1.remove(i)

n = int(input())
cond = []
for _ in range(n):
    cond.append(list(map(int, input().split())))
answer = int(1e9)
make_team([], 0, 0)
print(answer)

- itertools 라이브러리를 활요한 문제풀이

from itertools import combinations

n = int(input())
cond = []
for _ in range(n):
    cond.append(list(map(int, input().split())))
ls = list(combinations(list(range(n)),n//2))

team1_ls = ls[:len(ls)//2]
team2_ls = ls[len(ls)//2:][::-1]

result = 1e9

for i in range(len(ls)//2):
    team1_res = 0
    team2_res = 0
    
    team1 = team1_ls[i]
    team2 = team2_ls[i]
    for j in range(n//2):
        for k in range(n//2):
            team1_res += cond[team1[j]][team1[k]]
            team2_res += cond[team2[j]][team2[k]]
    result = min(result, abs(team1_res - team2_res))
print(result)

4. 코멘트

- 재귀적으로 알고리즘을 짜는 것은 itertools를 활용할 때보다 어려운 것 같다. 하지만 ietrtools를 활용했을 때 메모리를 너무 많이 사용하게 된다. 따라서 재귀적으로 문제를 푸는 방법도 알아둬야만 한다고 생각한다.

- 해당 문제에서 재귀적으로 코드를 구현하는 방법은 다시 한 번 더 복습해볼 필요가 있다.