[Python/파이썬] 백준 알고리즘 14889번 - 스타트와 링크 (백트래킹/Backtracking)

 

 

 

<풀이>

최초의 풀이는 조금 복잡하게 접근하였다.

"""
1. 아이디어
- 백트래킹으로 전수를 조사한다.
    - for문을 돌릴 때 마지막으로 선택한 선수보다 높은 번호의 선수들을 대상으로 한다.
    - 전체를 대상으로 돌리는게 아니라 N/2만큼 돌린다. (대칭이므로)
    - 깊이가 N/2에 도달하면 선택한 팀 구성을 대상으로 각각 팀의 능력치를 구한다.
    - 비교하여 현재 갖고 있는 최소값보다 작으면 교체한다.

2. 시간 복잡도
- NCN/2 * (N ** 2) = (N! / ((N - N/2)! * (N/2)!)) * (N/2 ** 2) ~= 70,000,000      -> 가능

3. 변수
- N : int
- S : int[][]
- 선택한 팀원 리스트 : int[]
- 능력치 차이 최소값 : int
"""
import sys
INF = sys.maxsize

input = sys.stdin.readline

N = int(input())
S = [[]]
for _ in range(N):
    S.append([0] + list(map(int, input().split())))

selected_team = []
min_diff = INF
def backtracking(num, last_player):
    if num == N // 2:
        unselected_team = []
        for i in range(1, N + 1):
            if i not in selected_team:
                unselected_team.append(i)
        team1_power = 0
        for player1 in selected_team:
            for player2 in selected_team:
                if player1 != player2:
                    team1_power += S[player1][player2]
        team2_power = 0
        for player1 in unselected_team:
            for player2 in unselected_team:
                if player1 != player2:
                    team2_power += S[player1][player2]
        global min_diff
        if min_diff > abs(team1_power - team2_power):
            min_diff = abs(team1_power - team2_power)
        return
    else:
        for selected_player in range(last_player + 1, N + 1):
            selected_team.append(selected_player)
            backtracking(num + 1, selected_player)
            selected_team.pop()

backtracking(0, 0)

print(min_diff)

전체 가능 조합을 모두 확인해봐야하는 문제이므로 백트래킹으로 접근했다.

selected_team이라는 리스트를 두고 넣었다 뺐다 하는 방식으로 진행했다.

중복되면 안되므로 else 문의 for 문에서는 마지막 인덱스의 + 1 부터 시작하는 것으로 하여 중복을 피해주었다.

if문에 걸렸을 때 처리는 직관적으로 생각나는대로 진행하였는데,

selected_team 리스트에 들어있는 값이 아닌 값들을 unselected_team에 넣고 각각의 팀 리스트를 이중포문으로 돌아 팀 능력치를 구했다. 그리고 두 능력치의 차를 구해 갖고 있는 최솟값과 비교하여 작다면 교체하는 방식으로 진행했다.

 

약간 지저분한 풀이라고 생각했는데 제출해보니 맞는 풀이였다.

더 깔끔한 풀이는 없을까 찾아보니 방문여부 리스트를 활용하는 방법이 있었다.

 

import sys
INF = sys.maxsize

input = sys.stdin.readline

N = int(input())
S = [[]]
for _ in range(N):
    S.append([0] + list(map(int, input().split())))

visit = [False] * (N + 1)
min_diff = INF

def backtracking(num, last_player):
    if num == N // 2:
        team1_power = 0
        team2_power = 0
        for player1 in range(1, N + 1):
            for player2 in range(1, N + 1):
                if player1 != player2:
                    if visit[player1] and visit[player2]:
                        team1_power += S[player1][player2]
                    elif not visit[player1] and not visit[player2]:
                        team2_power += S[player1][player2]
        global min_diff
        min_diff = min(min_diff, abs(team1_power - team2_power))
        return
    else:
        for selected_player in range(last_player + 1, N + 1):
            visit[selected_player] = True
            backtracking(num + 1, selected_player)
            visit[selected_player] = False

backtracking(0, 0)

print(min_diff)

위와 알고리즘 개념 자체는 똑같다.

다른 부분이 있다면 visit를 활용해 visit가 True인 것과 False인 것으로 팀을 나누는 방식이다.

덕분에 if문 아래가 꽤 깔끔하게 되었다.

같은 문제도 여러 방식으로 접근해 풀 수 있다는 점이 매력적인 것 같다.

 

 

 

<핵심 정리>

1. 전체를 조회해야 할 때 backtracking을 사용한다.

2. 백트래킹 알고리즘을 사용할 때 뽑은 요소 리스트를 활용하는 방법 외에도 visit 리스트를 활용하는 방법도 있다.