[Python] 스타트와 링크 - 백준 (DFS)

해당 글은 백준 14889번 문제 '스타트와 링크'를 다룬다.

문제

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

14889번: 스타트와 링크

 

설명

해당 문제는 itertools 모듈의 combinations 함수를 통해 완전 탐색으로 풀었을 때는 시간초과가 떴다.

인터넷의 도움으로 알아본 결과 백트래킹(DFS)로 풀어야 완전 탐색보다 훨씬 빨리 해결할 수 있다고 한다.

한 팀이 n//2로 구성되면, 나머지 팀은 자동으로 구성된다. 이를 이용해서 두 팀으로 나눌 수 있다.

 

- 완전탐색 : 모든 경우의 수를 탐색하는 방법

- 백트래킹 : 답이 될 수 없는 후보는 더이상 깊게 들어가지 않고 되돌아가는 방법

 

코드

def dfs(depth, index):
    global result

    # n//2 개 방문처리했으면 p1, p2 팀 능력치 차이 구하고 저장하기
    if depth == n // 2:
        p1, p2 = 0, 0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    p1 += arr[i][j]
                elif not visited[i] and not visited[j]:
                    p2 += arr[i][j]
        result = min(result, abs(p1 - p2))
        return

    for i in range(index, n):
        if not visited[i]:
            visited[i] = 1
            dfs(depth + 1, i + 1)
            visited[i] = 0

n = int(input())
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
visited = [0 for _ in range(n)]
result = int(1e9)

dfs(0, 0)
print(result)