[백준/Python] 스타트와 링크

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

14889번: 스타트와 링크

import sys

n = int(sys.stdin.readline()) # 사람 수
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] # 능력치 리스트
visited = [False] * n # 방문 여부 리스트
answer = 1e9 # 능력치 차이의 최소값

# DFS 수행 
def dfs(depth, now):
	global answer
	
	if depth == n // 2: # 팀 나누기가 끝났다면
		start, link =  0, 0
		
        # 스타트와 링크의 능력치 계산
		for i in range(n):
			for j in range(n):
				if visited[i] and visited[j]:
					start += graph[i][j]
				elif not visited[i] and not visited[j]:
					link += graph[i][j]

		answer = min(answer, abs(start - link)) # 능력치 차이의 최소값 갱신
					
    # 현재 노드의 인접 노드를 아직 방문하지 않았다면 DFS 수행
	for i in range(now, n):
		if not visited[i]:
			visited[i] = True
			dfs(depth + 1, i)
			visited[i] = False

dfs(0, 0)
print(answer)

1. 필요한 정보 입력 받는다

2. DFS를 수행한다

    2-1. 현재 탐색하는 노드의 방문을 True로 바꾼다

    2-2. 현재 탐색하는 노드의 인접 노드 중 아직 방문하지 않은 노드를 탐색한다 (DFS 수행)

    2-3. 팀 나누기가 끝났다면 (더 이상 탐색할 노드가 없는 경우) 스타트와 링크의 능력치를 계산하여 능력치 차이의 최소값을 구한다

    2-4. DFS 수행이 끝나면 현재 탐색하는 노드의 방문을 False 로 바꾼다

3. 답을 출력한다