백준 boj 15661 - 링크와 스타트 (파이썬, python)

https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

 

브루트포스와 백트래킹을 활용하여 풀었다.

가능한 조합을 모두 뽑아줘야 했지만,

시간제약의 관계로 dfs를 돌릴 때 for문을 쓰지 않는 방법으로 접근하였다.

조합을 뽑아 냈으면 start와 link로 나눠 차이를 구하고, 최소값을 갱신해줬다.

 

code

 

n = int(input())
stats = [list(map(int, input().split())) for i in range(n)]
visited = [0] * n
ans = 99999

def is_it():
    global ans
    start, link = 0, 0
    for i in range(n):
        for j in range(n):
            if visited[i] and visited[j]:
                start += stats[i][j]
            elif not visited[i] and not visited[j]:
                link += stats[i][j]
    ans = min(ans, abs(start - link))
    return

def resolve(iter):
    if iter == n:
        is_it()
        return
    visited[iter] = 1
    resolve(iter + 1)
    visited[iter] = 0
    resolve(iter + 1)
resolve(0)

print(ans)