[백준] 14889 스타트와 링크 python - 백트래킹, 조합

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

14889번: 스타트와 링크

 

예제 입력:
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제 출력:
0

예제 입력:
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

---

문제유형: 백트래킹, 조합

풀이

스타트팀과 링크팀의 능력치 차이의 최솟값을 구하는 문제이다.
+ 백트래킹은 아직 감이 안 잡혀서 처음에 백트래킹 유형이라는 것을 생각 못 하고 단순 수학 구현이라고만 생각했다. 백트래킹 연습이 더 필요할듯하다😭

 

상세 설명:

n * n 크기의 2차원 배열인 synergy를 만든다.
➡ 이 배열은 각 선수들의 시너지 값이 저장됩니다.
그리고 방문한 선수를 체크하기 위한 visited 배열과 최소 시너지 차이를 저장하기 위한 min_diff 변수를 초기화한다.

synergy = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
min_diff = 1e9  # 최소 시너지 차이를 저장하는 변수

백트래킹 함수를 정의하고 현재까지 뽑은 인원수(depth)와 시작점(start)을 인자로 받는다.
backtracking 함수는 현재까지 뽑은 인원수가 n/2명이 되면, 스타트와 링크 두 팀을 나누고, 각 팀의 시너지 값을 계산하여 최소 시너지 차이를 갱신합니다.

 

def backtracking(depth, start):
    global min_diff
    
    if depth == n // 2:  # 팀을 다 나누었을 경우

팀을 나누는 부분은 visited 배열을 활용하여 구현했다. backtracking 함수가 시작될 때, start 변수를 시작점으로 지정합니다. 그리고 start부터 n까지 반복하면서 visited[i]가 False인 경우에 한해 visited[i]를 True로 변경하고, backtracking 함수를 재귀적으로 호출한다. 재귀 호출이 완료되면 visited[i]를 다시 False로 변경하여 백트래킹을 수행한다.

for i in range(start, n):
        if not visited[i]:
            visited[i] = True
            backtracking(depth+1, i+1)
            visited[i] = False

 

 

정답 코드:

n = int(input())
synergy = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
min_diff = 1e9  # 최소 시너지 차이를 저장하는 변수

def backtracking(depth, start):
    global min_diff
    
    if depth == n // 2:  # 팀을 다 나누었을 경우
        start_team = []
        link_team = []
        for i in range(n):
            if visited[i]:
                start_team.append(i)
            else:
                link_team.append(i)
        
        # 팀 시너지 계산
        start_synergy = 0
        link_synergy = 0
        for i in range(n // 2):
            for j in range(i+1, n // 2):
                start_synergy += synergy[start_team[i]][start_team[j]] + synergy[start_team[j]][start_team[i]]
                link_synergy += synergy[link_team[i]][link_team[j]] + synergy[link_team[j]][link_team[i]]
        
        # 최소 시너지 차이 갱신
        min_diff = min(min_diff, abs(start_synergy - link_synergy))
        return
    
    # 팀 나누기
    for i in range(start, n):
        if not visited[i]:
            visited[i] = True
            backtracking(depth+1, i+1)
            visited[i] = False

backtracking(0, 0)
print(min_diff)

 

백트래킹 아직 연습이 필요하다...😭