[백준] 14889번 스타트와 링크 (python)

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

---

 

DFS로 풀었다. 이 문제를 딱 보자마자 모든 경우를 고려해야겠다고 판단했지만, 어떻게 코드를 구현해야 할지 몰랐다... 한 시간 정도 고민한 거 같다.

처음에는 인원을 짝지어서 넣고 바로 시너지를 계산해 줘야 되나 고민했는데 너무 복잡해지고 코드도 모르겠어서 다른 방법을 생각하려고 했다.

 

문제 풀이

1. 먼저 스타트팀과 링크팀의 인원이 같아질 때까지 선수를 넣는다. (이때 모든 경우를 고려하는 거다. 트리 형식으로 스타트팀과 링크팀에 넣어주었다.)
2. 그리고 스타트팀과 링크팀의 인원 수가 같아지면 각 팀의 시너지를 비교했다.
3. 이 시너지가 최소인 경우를 찾고자 했다. (DFS로 반복)

 

정답 코드

import sys
input = sys.stdin.readline

def diff(a, b):
    asum, bsum = 0, 0
    for i in range(n//2):
        for j in range(n//2):
            asum += board[a[i]][a[j]]
            bsum += board[b[i]][b[j]]

    return abs(asum - bsum)

def dfs(depth, a, b):
    global answer
    if depth == n:
        if len(a) == len(b):
            answer = min(answer, diff(a, b))
        return answer
    
    dfs(depth+1, a+[depth], b)		// 스타트팀을 선택하는 경우
    dfs(depth+1, a, b+[depth])		// 링크팀을 선택하는 경우

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

print(answer)

 

 

2024.07.08 리팩토링 코드

import sys
input = sys.stdin.readline

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
min_diff = 1e9

def get_diff(start, link):
    start_ability, link_ability = 0, 0
    for i in range(n//2):
        for j in range(n//2):
            start_ability += board[start[i]][start[j]]
            link_ability += board[link[i]][link[j]]
            
    return abs(start_ability - link_ability)

def dfs(player, start, link):
    global min_diff
    if player == n:
        if len(start) == len(link):
            min_diff = min(min_diff, get_diff(start, link))
        return
    
    dfs(player+1, start+[player], link)
    dfs(player+1, start, link+[player])

dfs(0, [], [])
print(min_diff)