Baekjoon [14889] 스타트와 링크 - python

문제 

14889번: 스타트와 링크

 

코드 풀이

import sys
from itertools import combinations
from collections import deque
input = sys.stdin.readline

# def bfs(list1):
    # start_node = list1[0]
    # que = deque()
    # que.append(start_node)
    # visited = []
    # visited.append(start_node)
    # sum1 = 0
    # while que:
    #     node = que.popleft()

n = int(input().strip())
matirx = []
for i in range(n):
    matirx.append(list(map(int,input().split())))
min_value = float('inf')
for combi in combinations(range(n),n//2):
    answer1= 0
    answer2 = 0
    combi = (list(combi)) # 조합 된 노드 탐색 시작
    another_combi = [i for i in range(n) if i not in combi] # 그외 조합되지 않은 노트 탐색 시작
    for r in combinations(combi, 2):  # 5
        answer1 += matirx[r[0]][r[1]]
        answer1 += matirx[r[1]][r[0]]
    for r in combinations(another_combi, 2):  # 6
        answer2 += matirx[r[0]][r[1]]
        answer2 += matirx[r[1]][r[0]]
    min_value = min(min_value, abs(answer1 - answer2))  # 7
print(min_value)

 

문제 접근

1. 주어진 matrix 길이의 /2 만큼 조합을 만들어 낸다. 

2. 이후 추출된 조합리스트에서 2개의 인덱스를 선정해서 값을 더한다.

3. 2개의 최소값을 비교하며 값을 도출한다.