백준 알고리즘 14889 (스타트와 링크) - python

백준 알고리즘 14889 (스타트와 링크) - python

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

14889번: 스타트와 링크

 

두 팀으로 나눠서 합산의 차이가 가장 적도록 만드는 문제.

백트래킹과 시간 효율이 중요한 문제이다.

(처음엔 시간초과로 멘붕이었다가 다시 해결)

 

[문제 풀이]

1. 절반(N//2명으로 구성)을 선택하여 조합을 생성 : DFS 탈출 조건

    -  나머지 N//2명은 자동으로 결정됨

2. 예외 처리

    - _min이 0일 경우에는 더 진행할 필요가 없음

3. 구해진 조합으로 _map을 대입하면서 _start와 _link 합산

    - 오름차순 비교 for문으로 시간 절약

    - 대각선 대칭인 S(j,i)도 더해주므로 오름차순만으로 처리됨

    -  visited 내에는 True/False만 존재하기 때문에 True/False 끼리의 조합 if문

4. 합산된 값의 차이와 _min 비교

5. 작은 값을 _min에 저장

 

import sys
N = int(sys.stdin.readline())
_map = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
visited = [False] * N
result = []
_min = 1e9

def diff():
    _start = 0
    _link = 0
    # 오름차순 비교 for문으로 시간 절약
    for i in range(N-1):
        for j in range(i+1, N):
            # True인 경우 _start팀
            if visited[i] and visited[j]:
                _start += _map[i][j]  # S(i,j)
                _start += _map[j][i]  # S(j,i)
            # False인 경우 _link팀
            elif not visited[i] and not visited[j]:
                _link += _map[i][j]
                _link += _map[j][i]
    return abs(_start - _link)

def dfs(depth, idx, N):
    global _min
    if depth == N // 2:  # 절반만 선택
        diff_result = diff()
        _min = min(_min, diff_result)
        if _min == 0:  # 0이면 바로 출력
            print(_min)
            exit(0)
        return
    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            dfs(depth+1, i+1, N)
            visited[i] = False
    return

dfs(0, 0, N)
print(_min)