BOJ(스타트와링크)(14889)

스타트와 링크 14889

N명을 N/2명씩 두 팀으로 나누려고 한다. (4<=N<=20 , N은 짝수)
두 팀의 능력치를 구한 다음, 차이의 최소값을 구하는 문제
S[i][j] = i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치
팀의 능력치 : 팀에 속한 모든 쌍의 S[i][j]의 합

3단계

N명을 2분의 N명씩 나누는 방법의 수 : 20 C 10 -> 100만 보다 작을 것. (N<=20)이므로 경우의 수가 크지 않다.
팀의 능력치를 구하는 건 어떨까 ? 팀을 정한 다음에, s[i][j]의 합을 구하면 될 것
모든 방법을 어떻게 만들 것인가 ?

순열을 사용하는 방법을 알아보자.
팀 0, 팀 1
N개의 총 수 중에서 0을 2분의 n개를 넣고, 1을 2분의 n개를 넣게 되면 모두 2팀으로 만들 수 있다.

def next_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] <= a[i-1]:
        j -= 1

    a[i-1],a[j] = a[j],a[i-1]

    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

    return True

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
b = [0 if i < n/2 else 1 for i in range(n)]
ans = 2147483647
while True:
    first = []
    second = []
    for i in range(n):
        if b[i] == 0:
            first.append(i)
        else:
            second.append(i)
    one = 0
    two = 0
    for i in range(n//2):
        for j in range(n//2):
            if i == j:
                continue
            one += a[first[i]][first[j]]
            two += a[second[i]][second[j]]
    diff = abs(one-two)
    if ans > diff:
        ans = diff
    if not next_permutation(b):
        break
print(ans)

combinations 이용한 풀이

import sys
import itertools

N = 0
arr = []

def team(member):
    allMember = [i for i in range(N)]
    start_team = []
    link_team = []

    ## 멤버 선택
    for i in allMember:
        if i in member:
            start_team.append(i)
        else:
            link_team.append(i)

    start_sum = 0
    for i in start_team:
        for j in start_team:
            start_sum += arr[i][j]

    link_sum = 0
    for i in link_team:
        for j in link_team:
            link_sum += arr[i][j]

    return abs(start_sum - link_sum)

def solve(members):
    ## 모든 경우의 수 뽑기
    combination_members = itertools.combinations(members, int(N/2))
    selected_members = list(combination_members)
    length = int(len(selected_members)/2)

    minVal = sys.maxsize
    for member in selected_members[:length]:
        minus = team(member)

        if minVal > minus:
            minVal = minus

    print(minVal)


if __name__ == '__main__':
    N = int(sys.stdin.readline())
    members = [i for i in range(N)]

    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))

    solve(members)

백트래킹 : 브루트 포스 알고리즘에서 재귀 함수를 이용해서 문제를 풀 수 있다. 그 때 재귀 함수는 어떤 특징이 있냐면, 절대 정답을 못 구할 때, 함수 호출을 더이상 진행시키지 않고 종료시켜버리는 것을 백트래킹이라고 한다.
문제에 따라서 종료가 정리된다.
스타트와 링크를 백트래킹으로 풀어보자.
N명을 N/2명씩 2팀으로 나눈다.
1~N명이 있고, 이 사람들은 1팀 또는 2팀으로 들어가야 한다.
1번 사람이 1팀에 들어갔을 때, 2팀에 들어갔을 때,
2번 사람이 1팀에 들어갔을 때, 2팀에 들어갔을 때, 쭉쭉 만들어본다.
이 경우의 수를 만들어보는 것을 재귀함수로 해결할 수 있다.

함수 설명

go(index,first,second)
- index번째 사람을 어떤 팀에 넣을지 결정해야함
- 1번 팀과 2번 팀에 속한 사람이 first,second에 들어있음
정답을 찾은 경우
- index == n
다음 경우
- 1번팀 go(index+1,first,second) -> 1번 팀에 들어갔을 때 만들어보고 나와서
- 2번팀 go(index,first,second) -> 2번 팀에 들어갔을 때를 만들어본다
- 두 경우 모두 호출 전에 first 또는 second에 index를 넣고, 호출 후에 빼는 과정이 필요

소스코드

팀의 능력치 모두 입력 받고,
두 팀엔 사람이 없으니까, 0번부터 n-1까지니까, 0번 인덱스의 사람을 두 팀 중 하나에 넣어야 하고
1번에는 first란 사람들이, 2번 팀에는 second란 사람들이 있다.
정답을 찾은 경우 -> 두 팀이 모두 n/2이란 것을 의미
두 팀의 능력치의 차이를 구하는 거여서, 차이는 0보다 큰 값이 나올 수 밖에 없기에, -1온 것은 불가능.
1번 팀과 2번 팀의 사이즈가 n/2이 아니면, 제외 해야한다.
모든 사람의 능력치의 합을 구해서 차이를 구해서 리턴해준다.
사람을 넣는 것은 index번째 -> 1번팀
아래 부분은 index번째 -> 2번팀

불가능한 경우

한팀에 들어가는 사람의 수가 n/2을 넘은 경우가 있을 수 있다.
굳이 그럴 필요가 없다. 탐색을 하면서 확인을 해보는 것이다.

def go(idx, first, second):
    if idx == n:
        if len(first) != n//2:
            return -1 # 불가능하니까 -1 리턴
        if len(second) != n//2:
            return -1
        t1, t2 = 0, 0
        for i in range(n//2):
            for j in range(n//2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1-t2)
        return diff
    ans = -1
    # 1번 팀에 넣는 경우
    t1 = go(idx+1, first+[idx], second)
    # ans == -1이 의미 -> 아직 정답을 구하지 않은 것
    # t1 != -1 -> idx에 넣은 사람을 first에 넣는게 가능하고
    # 내가 가지고 있는 정답보다 작으면 ans에 최솟값 넣어주기
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    # 2번 팀에 넣는 경우
    t2 = go(idx+1, first, second+[idx])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans


n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]  # 문제에서 s라고 했으니 s로 정의
print(go(0, [], []))

가지치기

def go(index, first, second):
    if index == n:
        if len(first) != n//2:
            return -1
        if len(second) != n//2:
            return -1
        t1 = 0
        t2 = 0
        for i in range(n//2):
            for j in range(n//2):
                if i == j:
                    continue
                t1 += s[first[i]][first[j]]
                t2 += s[second[i]][second[j]]
        diff = abs(t1-t2)
        return diff
    if len(first) > n//2:
        return -1
    if len(second) > n//2:
        return -1
    ans = -1
    t1 = go(index+1, first+[index], second)
    if ans == -1 or (t1 != -1 and ans > t1):
        ans = t1
    t2 = go(index+1, first, second+[index])
    if ans == -1 or (t2 != -1 and ans > t2):
        ans = t2
    return ans

n = int(input())
s = [list(map(int,input().split())) for _ in range(n)]
print(go(0, [], []))

다른 풀이과정

import sys
n = int(sys.stdin.readline())
a = [list(map(int, input().split())) for _ in range(n)]
c = [False]*n
ans = 1e9

def solve(cnt, idx):
    global ans
    if idx == n:
        return
    if cnt == n//2:
        s1, s2 = 0, 0
        for i in range(n):
            for j in range(n):
                if c[i] and c[j]:
                    s1 += a[i][j]
                if not c[i] and not c[j]:
                    s2 += a[i][j]
        ans = min(ans, abs(s1-s2))
        return
    c[idx] = True
    solve(cnt+1, idx+1)
    c[idx] = False
    solve(cnt, idx+1)

solve(0, 0)
print(ans)


출처: https://rebas.kr/754 [PROJECT REBAS]

참고자료 codeplus