[n14889] 스타트와 링크 in python

---

보자마자 백트래킹이 떠올랐던 문제!

백트래킹의 원리는 이해했는데

자꾸 방문처리 체크하는 부분을 빼먹어서 

애를 먹는다;

 

 

백트래킹

dfs(depth,now):
	if depth==n:
    	return #함수 종료
    for i in range(n):
        if visited[i]:
            continue
        visited[i]=1
        dfs(depth+1,now)
        visited[i]=0

 

문제를 풀긴 풀었는데

시간이 7140ms..?

허허..

 

최대한 필요 없는 과정 제외했다고 생각했는데

ㅠㅠ...

 

s_team에는 스타트팀에 들어간 팀원의 번호

t_team에는 링크팀에 들어간 팀원의 번호를 넣었다.

 

func함수에서 

각 팀의 능력치를 계산하고

최소인지 아닌지 판별하여

answer에 값을 넣는다.

 

 

n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
answer = 1000000000
visited = [0] * n
cnt = 0


def func(s_team, t_team):
    global answer
    s_sum = 0
    t_sum = 0
    for i in range(len(s_team)):
        for j in range(i + 1, n//2):
            s_sum += s[s_team[i]][s_team[j]] + s[s_team[j]][s_team[i]]
            t_sum += s[t_team[i]][t_team[j]] + s[t_team[j]][t_team[i]]
    answer = min(answer, abs(s_sum - t_sum))


def dfs(next, cnt):
    if cnt == n // 2:
        s_team = [idx for idx, i in enumerate(visited) if visited[idx] == 1]
        t_team = [idx for idx, i in enumerate(visited) if visited[idx] == 0]
        func(s_team, t_team)
        return

    for i in range(next, n):
        if visited[i]:  # *****
            continue
        visited[i] = 1
        dfs(i + 1, cnt + 1)
        visited[i] = 0


dfs(0, cnt)
print(answer)

 

일단 for문과 불필요한 연산이 너무 많아서

실행시간이 많이 나온 듯 하다..!

 

s_sum,t_sum 부분이.. ㅎ..

---

좀 더 효율적인 코드를 찾아 떠났다.

from itertools import combinations
import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
each = [sum(x) + sum(y) for x, y in zip(arr, zip(*arr))]
total = sum(each) // 2

print(min(abs(total - sum(each[e] for e in c)) for c in combinations(range(1, n), n // 2)))

여기서는 itertools 라이브러리의 combinations함수를 이용하였다.

zip 함수 관련 내용은 

https://eboong.tistory.com/321

[제주코딩베이스캠프] 눈떠보니 코딩테스트 전날 | 코딩테스트 Final 메서드 정리

zip(*arr)을 하면 배열을 뒤집을 수 있다.

i/j	1	2	3	4
1		4	7	3
2	1		1	4
3	2	7		5
4	3	3	2

 

zip(arr,zip(*arr))

-> 기존 배열과 순서를 뒤집은 배열을 묶어주는 작업이다.

즉 Sij=[Sij,Sji]로 만들어주는 과정

 

each=>

[1,2,3,4,7,3],

[4,5,6,1,1,4],

[7,1,2,2,7,5],

[3,3,2,3,4,5]

 

each=[20,21,22,23]

total=sum(each)//2

 

 

combinations(1~3,4//2)

(1,2) , (1,3), (2,3)

 

 

(1,2)

abs(total-(each[1]+each[2]))

each의 반값에서 each[1],each[2]를 빼면

each[3],each[4]와의 차이가 바로 나온다.

 

total=86 // 2 = 43

43-20-21=2

print(min(abs(total - sum(each[e] for e in c)) for c in combinations(range(1, n), n // 2)))