백준 - 스타트와 링크(14889번 파이썬 풀이)

백트래킹에서의 마지막 문제였는데 백트래킹 알고리즘은 정말 어려웠다. 먼저 틀린 예제를 보자.

import sys
input = sys.stdin.readline

def dfs(a):
	global result
	if len(s) == n//2:
		lt, st = 0, 0
		for i in range(1, n+1):
			for j in range(1, n+1):
				if i not in s and j not in s:
					lt += arr[i-1][j-1]
				elif i in s and j in s:
					st += arr[i-1][j-1]
		result= min(result, abs(lt-st))
		return

	for i in range(a, n+1):
		if i not in s:
			s.append(i)
			dfs(i)
			s.pop()

n=int(input())
arr=[list(map(int, input().split())) for _ in range(n)]
s=[]
result=int(1e9)
dfs(1)

print(result)

이 코드는 시간초과가 나와서 틀렸는데 그 이유는 앞 문제임 N과 M 문제에서 사용했던 방식처럼 모든 숫자를 순회하며

계산하는 방식으로 풀어서 시간초과가 나왔다.

이것을 해결하기 위해서는 전체를 순회하기보다는 4개의 숫자가 팀이 되었는지 안 되었는지를 따지고 풀면 시간초과가 안 뜬다. 밑에 코드를 보자

import sys
input = sys.stdin.readline

def dfs(a, idx):
	global result
	if a == n//2:
		lt, st = 0, 0
		for i in range(n):
			for j in range(n):
				if visited[i] and visited[j]:
					lt += arr[i][j]
				elif not visited[i] and not visited[j]:
					st += arr[i][j]
		result= min(result, abs(lt-st))
		return

	for i in range(idx, n):
		if not visited[i]:
			visited[i] = True
			dfs(a+1, i+1)
			visited[i] = False

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

print(result)

알고리즘 자체는 위에 코드와 비슷하지만 위에 코드는 배열을 선언해 모든 경우의 수를 대입하는 반면에 이 알고리즘은 

팀에 소속된 선수와 안 된 선수를 구분하기 위해서 boolean 배열을 통해 해결해 주었다.