[백준] 14889번 스타트와 링크(파이썬)

문제

14889번: 스타트와 링크

코드

combinatiuons

from itertools import permutations, combinations
import sys
input = sys.stdin.readline

N = int(input())

graph = [list(map(int, input().split())) for _ in range(N)]

# p = permutations(range(0, N), N//2)
p = list(combinations(range(N), N//2))
# print(list(p))
A = []
B = []

for i in range(len(p)//2):
    A.append(p[i])
    B.append(p[-i-1])

min_score = float('inf')
for i in range(len(A)):
    a_score, b_score = 0, 0
    for j in range(len(A[i])-1):
        for k in range(j, len(p[i])):
            a_score += graph[A[i][j]][A[i][k]] + graph[A[i][k]][A[i][j]]
            b_score += graph[B[i][j]][B[i][k]] + graph[B[i][k]][B[i][j]]
    if min_score > abs(a_score - b_score):
        min_score = abs(a_score - b_score)
print(min_score)

해설

permutations : 순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말한다.  (A, B) (B, A)는 달라서 따로 나온다
combinations : 조합의 순서를 고려하지 않고 나타내는 조합(팀을 만들 때 많이 사용)

combinations으로 조합을 만들어서 그 조합을 2개로 나누어주었다. (p[0]과 p[-1]은끼리 짝이다.)

그리고 해당 조합의 갯수만큼 돌고 그 조합을 브루트포스 알고리즘(전체를 도는 알고리즘)으로 전체를 돌게해주었다.

 

위 방법으로 풀고 내장 모듈을 사용하지 않고 조합을 만드는 법을 알아야할 것 같아서 다른 분의 코드를 보고 다른 코드도 만들어 보았다.

코드의 속도는 내장 모듈을 사용한 위 코드가 더 빠르니 참고하길 바란다.

 

코드

DFS

def DFS(x, y):
    global min_score
    if x == N // 2:
        a_score, b_score = 0, 0
        for i in range(N):
            for j in range(N):
                if visitied[i] and visitied[j]:
                    a_score += graph[i][j]
                elif not visitied[i] and not visitied[j]:
                    b_score += graph[i][j]
        if min_score > abs(a_score - b_score):
            min_score = abs(a_score - b_score)

    for i in range(y, N):
        if not visitied[i]:
            visitied[i] = True
            DFS(x+1, i+1)
            visitied[i] = False

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
visitied = [False for _ in range(N)]
min_score = float('inf')
DFS(0, 0)

print(min_score)

해설

DFS를 사용하는 코드였다. visited로 N//2개이상 들렸다면 함수를 시작한다. 위 코드와는 다르게 전체를 돌기 때문에 graph[i][j]만 해주면 되었다.