14889

날짜 : 2022. 10. 12

사용 언어 : python

 

문제

 

 

코드

import sys

def dfs(depth, idx):
    global result
    if depth == (n//2): # 스택이 다 찬 경우 능력치 비교
        team1, team2 = 0, 0 # start, link의 능력치 설정
        for i in range(n):
            for j in range(n):
                if visit[i] and visit[j]:
                    team1 += s[i][j] # true -> start
                elif not visit[i] and not visit[j]:
                    team2 += s[i][j] # false -> link
        result = min(result, abs(team1-team2))
        return
    for i in range(idx, n):
        if visit[i]:
            visit[i] = False
            #start.append(i) # start 스택 채우기(True)
            dfs(depth+1, i+1)
            #start.pop()
            visit[i] = True

n = int(sys.stdin.readline())
visit = [True] * n # 사용여부
#start = []
result = int(1e9) # 능력치 차이

# 좌표 입력
s = []
for _ in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    s.append(tmp)

dfs(0, 0) # 재귀의 깊이, 반복지점
print(result)

 

 

알게된 점

- start, link 리스트를 만들고 두 스택이 전부 찼을 때 일일이 결과값을 구함으로써 답을 구하려고 했지만 시간초과가 나왔다.

- start 리스트를 없애고 단순 방문여부만을 체크해서 답을 구하려고 했지만 시간초과

- dfs에서 depth와 idx로 반복문을 처음부터 하지 않게 하기 위해서 시작했지만 14%에서 틀림

- 알고보니 dfs(depth+1, idx+1)로 기입해서 틀린거였나 했지만 고쳐도 틀림

- 그러고 맨 처음 result값을 999에서 int(1e9)로 수정했더니 드디어 맞았다.

- 풀이방식은 맞았지만 최적화 작업을 확실하게 하지 못해서 꽤 애를 먹은 것 같다.

 

 

참고 사이트

- https://developer-ellen.tistory.com/50

BOJ - 스타트와 링크 14889번 (python)