2022.01.2

백준 14889 스타트와 링크

# 14889 스타트와 링크

# dfs = 가능한 팀의 경우의 수를 모두 추출한다. 
def dfs():
    if len(R) == (N//2):
        start.append(R[:])
        link.append(list(set(num) - set(R[:])))
    for i in range(1,N+1):
        if i > R[-1]:
            R.append(i)
            dfs()
            R.pop()

M = []
N = int(input())
for i in range(N):
    M.append(list(map(int, input().split())))
num = [i for i in range(1,N+1)]

# 모든 경우에 팀 안에 1번이 들어있으므로 1번이 들어간 모든 경우의 수를 출력하면 된다.
R = [1]
start = []
link = []
dfs()

# result = 스타트팀과 링크팀 점수차를 저장하는 리스트
result = []

for i in range(len(start)):
    start_sum = 0
    link_sum = 0
    for j in range(N//2):
        for _ in range(N//2):
            start_sum += M[start[i][j]-1][start[i][_]-1] 
            link_sum += M[link[i][j]-1][link[i][_]-1]
    result.append(abs(start_sum -link_sum)) 
print(min(result))

처음에 함수 dfs()에서 R을 저장하려고 할 때, 저장해서 출력하면 빈 리스트만 나와서 당황했었다.

그 이유는 R의 요소를 저장한게 아니라 R 자체를 저장한 것이라 pop()이 되어서 그렇다는데 정확하게 이해하지 못했다.

아무튼 그걸 해결하기 위해서 R[:]을 취해서 요소를 저장해줬더니 문제를 해결할 수 있었다.

문제풀이의 아이디어는 일단 팀으로 만들 수 있는 모든 경우의 수를 찾아내고

또 그팀 안에서 점수를 낼 수 있는 모든 조합을 계산한 다음, 두 팀 간 점수 차의 절댓값을 구하면 된다고 생각했다.

dfs() 함수를 통해서 가능한 start와 link 팀의 경우의 수를 구했고 각 인덱스는 서로 대비된다.

start팀에 start[1]의 요소가 배정되면 link팀에는 전체 팀원에서 start[1]을 뺀 link[1]이 배정된다.

그리고 경우의 수를 구할 때 R이라는 임의의 리스트에 1을 넣어둔 이유는 어떤 경우라도 1번은 둘 중 한 팀에

무조건 들어가 있어야 하기 때문에 그냥 1번이 들어갈 수 있는 모든 팀의 경우의 수를 뽑아내면 된다고 생각했다.