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

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

728x90

https://www.acmicpc.net/problem/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. 답을 출력한다

728x90

from http://soohyun6879.tistory.com/204 by ccl(A) rewrite - 2021-09-18 13:26:40