백준 14889 파이썬 스타트와 링크

백준 링크:https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

dfs로 풀려했었는데 이해가 잘 안됐었다. 특히 예제 2번 6을 입력받았을떄 어떻게 해야하나 걱정했었는데

 

그냥 모든 조합을 구하면 되는거였다.

 

dfs로 visit 값을 구하면서 cnt가 만약 n//2값이 된다면 이중 for문을 작동시켜서 서로 짝일 경우에

start와 link 따로 계산해서 abs(start-link) (절대값)으로 계산했다.

n=int(input())
matrix=[]
for i in range(n):
    matrix.append(list(map(int,input().split())))

visited=[0 for i in range(n)]
result=[]

min_result=1000000000

def dfs(idx,cnt):
    global  min_result

    if cnt == (n//2):
        start,link = 0,0
        for i in range(n):
            for j in range(n):
                if visited[i] == 1 and visited[j] == 1:
                    start += matrix[i][j]
                elif visited[i] == 0 and visited[j] == 0:
                    link += matrix[i][j]
        min_result = min(min_result, abs(start-link))


    for i in range(idx,n):
        if visited[i] == 0:
            visited[i] = 1
            dfs(i+1 , cnt + 1)
            visited[i] = 0

dfs(0,0)
print(min_result)

 

만약 n == 4 일 경우의 수

첫번째 [1,1,0,0] 의 경우

matrix[0][1] , matrix[1][0] 이 짝

matrix[2][3],  matirx[3][2] 이 짝

 

 

n == 6 일 경우

첫번째 [1,1,1,0,0,0] 의 경우

matrix[0][1] , matrix[1][0], matrix[0][2], matrix[2][0] 이 짝

matrix[3][4],  matirx[4][3], matrix[3][5], matrix[5][3] 이 짝

따로 다 더하고 빼주면 끝