14889번 스타트와 링크

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

아이디어

팀을 나누기 위해 방문하지 않았다면 True로 바꾸고 함수를 다시 실행한다. (visited가 True라면 스타트팀, False라면 링크팀)

for i in range(idx, n):
	if not visited[i]:
		visited[i] = True
        dfs(cnt+1, i+1)
        visited[i] = False

현재 몇 명이 팀에 있는지 cnt, 중복탐색 방지를 위한 idx

백트래킹을 사용한 방법은 idx = 0, visited = [True, False, False, False], cnt=1일 때, dfs(1, 1) 재귀이고 그렇게 되면 visited = [True, True, False, False]가 된다. 팀원을 절반으로 나누었으므로 능력치를 계산한 후, 다시 dfs(1, 1) 코드로 돌아오게(back) 되고 visited[1] = False가 된다. 그런 다음 visited = [True, False, True False] 가 된다.

if cnt == n // 2: # 팀이 절반으로 나누어졌다면 능력치 계산
        start, link = 0, 0
        for i in range(n-1):
            for j in range(i+1, n):
                if visited[i] and visited[j]:
                    start += graph[i][j] + graph[j][i]
                elif not visited[i] and not visited[j]:
                    link += graph[i][j] + graph[j][i]
        result = min(result, abs(start - link))

cnt == n//2가 되면 팀이 절반씩 잘 나누어졌으므로 각 팀의 능력치 차이를 계산한다.
ex) visited = [True, False, True, False] 0번과 2번이 start 팀, 1번과 3번이 link팀이 된다. (문제에서는 1번팀부터 시작하지만 나는 0번부터 시작했다.)

---

코드

import sys
input = sys.stdin.readline

def dfs(cnt, idx):
    global result, n
    if cnt == n // 2: # 팀이 절반으로 나누어졌다면 능력치 계산
        start, link = 0, 0
        for i in range(n-1):
            for j in range(i+1, n):
                if visited[i] and visited[j]:
                    start += graph[i][j] + graph[j][i]
                elif not visited[i] and not visited[j]:
                    link += graph[i][j] + graph[j][i]
        result = min(result, abs(start - link))

    else: # 팀 안나누어졌으면 팀 나누기
        for i in range(idx, n):
            if not visited[i]:
                visited[i] = True
                dfs(cnt+1, i+1)
                visited[i] = False
    return result

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [False]*n
result = float('inf')
print(dfs(0, 0))