스타트와 링크 풀이

문제 링크: https://www.acmicpc.net/problem/14889

백준 알고리즘 기초 2/2 530에서 4번째 - 14889번 스타트와 링크를 풀어보았다.

 

풀이: https://pottatt0.tistory.com/m/entry/%EB%B0%B1%EC%A4%80-14889-%ED%95%B4%EC%84%A4-python-%EC%8A%A4%ED%83%80%ED%8A%B8%EC%99%80-%EB%A7%81%ED%81%AC 를 참고했다.

 

C++

 

Python

def dfs(l,idx):
	global cnt
	if l==n//2:
		a=0
		b=0
		for i in range(n):
			for j in range(n):
				if visit[i] and visit[j]:
					a+=arr[i][j]
				elif not visit[i] and not visit[j]:
					b+=arr[i][j]
		cnt=min(cnt,abs(a-b))
		return
	for i in range(idx,n):
		if not visit[i]:
			visit[i]=True
			dfs(l+1,i+1)
			visit[i]=False

n=int(input())
arr=[list(map(int,input().split())) for i in range(n)]
visit=[False for i in range(n+1)]
cnt=1000000000000
dfs(0,0)
print(cnt)

Java