[BOJ] 14889. 스타트와 링크

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

14889번: 스타트와 링크

 

 

1. 해결방법

"""
1. 아이디어
- 각 팀을 n // 2로 나누어서 처리한다.
- 2중 for문을 사용해서 선수를 추출한다. 방문기록 체크
- 먼저 Start Team을 n // 2만큼 append하고, 재귀 종료 지점으로 이동한다.
- Start Team에 append된 팀을 제외한 나머지 팀을 Link Team에 append 한다.
- 각 팀의 시너지 합을 구하고 최소값이 되도록 비교한다.

2. 시간복잡도
-

3. 자료구조
- 백트래킹 : 재귀
- 배열 : bool[]
"""

 

 

2. 정답코드

입력 예제(1)

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

출력 예제(1)

0

 

입력 예제(2)

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

출력 예제(2)

2

 

입력 예제(3)

8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

출력 예제(3)

1

 

 

코드

import sys
input = sys.stdin.readline


# input
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
chk = [False] * (n + 1)

start = []
link = []
min_v = 0
answer = int(1e9)


# recur
def recur(num):
    global min_v, answer

    # 재귀 종료 지점
    if num == n // 2:
        start_sum = 0
        link_sum = 0

        # Start Team에 들어간 수를 제외한 수를 Link Team에 append.
        for i in range(1, n + 1):
            if i not in start:
                link.append(i)


        # 각 팀의 합
        for i in range((n // 2) - 1):
            for j in range(i + 1, n // 2):
                start_sum += graph[start[i] - 1][start[j] - 1] + graph[start[j] - 1][start[i] - 1]
                link_sum += graph[link[i] - 1][link[j] - 1] + graph[link[j] - 1][link[i] - 1]

        min_v = abs(start_sum - link_sum)
        # 최소값 비교
        answer = min(answer, min_v)
        # link 리스트에 원소 값이 남아있기 때문에 하나의 경우가 끝나면 리스트 초기화 시켜줌.
        link.clear()
        return


    # 재귀
    for i in range(1, n + 1):
        if chk[i] == False:
            if len(start) > 0 and start[len(start) - 1] > i: continue
            chk[i] = True
            start.append(i)
            recur(num + 1)
            chk[i] = False
            start.pop()

# main
recur(0)
print(answer)

 

이 문제를 풀 때는 아직 알고리즘 입문자라서 해결하는 것도 어려웠지만 무엇보다도 시간초과가 걸려서 시간을 더 오래 잡아먹었다.
for문을 조건을 걸어 최소화 해야하는데 그 부분이 어려워서 힘들었다.

시간을 줄이는 방법을 더 해보야겠다.