[백준/Python] 14889- 스타트와 링크

BlackHan·2024년 1월 3일

알고리즘

14889 - 스타트와 링크

1. 문제 해석

N명의 축구 선수가 있고, 각 선수들의 능력치가 주어진다. 팀을 두 개로 나누어 각 팀의 능력치를 구한 후, 두 팀의 능력치 차이가 최소가 되도록 팀을 나누는 문제이다.

N명의 선수를 두 팀으로 나누는 모든 경우를 고려하고, 각 경우에 대해 두 팀의 능력치를 계산하여 차이를 최소화하는 것이 목표이다.

예를 들어, N=4일 때, 1, 4번이 스타트 팀, 2, 3번이 링크 팀에 속한 경우에는 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고, 이 값이 최소이다.

2. 문제 접근

N의 범위가 4~20 까지 주어졌고, 시간제한은 2초이기 때문에 어떤 알고리즘을 이용해도 여유로워 보였다. 두 팀으로 나누는 모든 경우를 고려해도 2^20 알고리즘으로 1초 이내 해결이 가능할 것으로 보아 dfs를 이용.

다만, 방문한 선수들에 대한 상태를 저장하고, N/2명으로 이루어진 팀이기에 이를 이용하여 불필요한 경우의 수를 배제하거나 최적해를 찾아내는 백트래킹을 사용한다.

3. 알고리즘 풀이

트리형태로 각 팀을 start와 link로 나눔
종료 조건 : 트리의 깊이가 N이 된다면 멈추고, 각 팀의 능력치를 계산
start 팀이 됐을 때와 link 팀이 됐을 때를 나눠서 계속 호출

문제에서는 N이 짝수이지만, 간단하게 N = 3일 때를 예시로 들어본다.
1번을 start 팀으로 갈 경우와 link 팀으로 갈 경우를 나눈다. 마찬가지로 2번과 3번도 나누어 간다.
depth가 N이 되었을 때는 모두 탐색을 한 것이기에 return한다.

N=int(input())
arr=[list(map(int,input().split())) for _ in range(N)]
answer = 100 * N * N # 최대 능력치 100이기에 최대값

def bt(depth, sTeam, lTeam): # (트리 깊이, start 멤버 리스트, link 멤버 리스트)
    global answer
    if depth == N : # depth N까지 모두 확인했다면,
        if len(sTeam) == len(lTeam): # 각 팀의 멤버수가 같은지 확인
            start, link = 0, 0
            for i in range(N//2):
                for j in range(N//2):
                    start += arr[sTeam[i]][sTeam[j]]
                    link += arr[lTeam[i]][lTeam[j]]
            answer = min(answer, abs(start - link)) #최소 차이 찾기
        return
    # depth N이 되기전까지 가능한 수를 모두 넣는다.
    bt(depth+1, sTeam+[depth], lTeam) # start Team에 갈 경우
    bt(depth+1, sTeam, lTeam+[depth]) # link Team에 갈 경우
bt(0,[],[]) #depth 0 , sTeam lTeam은 빈 상태로 시작
print(answer)

번호를 1부터 N까지로 배정했기 때문에 depth를 다음 사람의 번호로 치부했다.

bt(depth+1, sTeam+[depth], lTeam) 는 다음 사람을 startTeam에 배정했을 때를 호출한다.
bt(depth+1, sTeam, lTeam+[depth]) 는 linkTeam에 배정했을 때를 호출한다.

(2) visited[ ]을 이용한 다른 풀이

# 입력을 받는다.
N=int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
visited = [False] * (N+1)
result = 2e9 # 가장 큰 수를 넣어둔다.

def bt(depth, idx): # depth는 현재까지 선택한 팀의 수 이다.
    global result
    if depth == (N//2): # N//2 만큼 선택되면
        start, link = 0, 0
        for i in range(N):
            for j in range(i+1,N):
                if visited[i] and visited[j]: #선택했다면
                    start += (arr[i][j]+arr[j][i]) 
                # 선택 안되었다면, 
                elif not visited[i] and not visited[j]: 
                    link += (arr[i][j]+arr[j][i])
        result = min(result,abs(start-link)) #최소 차이 찾기
        return
    for i in range(idx, N) : 
        if not visited[i]: # 아직 선택안했다면,
            visited[i]=True # 방문처리
            bt(depth+1, i+1) # 백트래킹을 하고나서
            visited[i]=False # 다시 방문을 안한것으로 한다.
bt(0,0)
print(result)