[Python](DFS) 백준 14889번 : 스타트와 링크

---

<접근 방법>

1. 문제에 있는 보드 형태 그대로 이차원 배열을 board에 담는다.
2. 항상 N//2명을 가진 두 팀으로 나누어지므로, dfs를 짤 때 a팀에 들어가는 경우와 그렇지 않은 경우에는 b팀으로 들어가는 경우로 나눈다.
3. N//2명을 가지는 두 팀으로 나누어졌을 때만, answer를 갱신할 수 있도록 한다.
4. (DFS 안) 각 팀의 능력치를 구하기 위해 이중 for문을 이용해 계산한다. answer 갱신은 두 팀의 능력치의 최소값으로 둔다.

def dfs(n, team_a, team_b):
    global answer
    if n == N:
        if len(team_a) == len(team_b):  # 두 팀 모두 N//2명을 가질 때
            a_score, b_score = 0, 0     # 각 팀의 능력치
            for i in range(N//2):
                for j in range(N//2):
                    a_score += board[team_a[i]][team_a[j]]
                    b_score += board[team_b[i]][team_b[j]]
            answer = min(answer, abs(a_score-b_score))  # 두 팀의 능력치 차이 최소값 갱신
        return
    dfs(n+1, team_a+[n], team_b)    # 사람이 team_a에 속할 때
    dfs(n+1, team_a, team_b+[n])    # 사람이 team_b에 속할 때


N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
answer = 1e9    # 임시로 최대값 설정(최소값을 구하는 것이 우리의 목표이므로)
dfs(0, [], [])
print(answer)

이해가 안되는 부분이 있으면 질문 주세요. 감사합니다.