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

1. 문제소개

• 브루트포스, 백트래킹 유형 문제에 해당한다.

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

2. 코드

import itertools
import sys
input = sys.stdin.readline

# variables for backtracking
VISIT = []
M = []
N = 0 
MIN_SCORE = 100


def set_test_case():
    M = []
    N = int(input())
    for i in range(0,N):
        line  = input().split(' ')
        x = list(map(lambda x: int(x),line))
        M += [x]
        
    return M,N


# return Score difference of Two Team
def comparison_team(A,B,M):
    A_score=  0 
    B_score = 0 
    for i in A:
        DIFF = set(A)- set ([i])
        for j in DIFF:    
            A_score += M[i][j]
    for i in B:
        DIFF = set(B)- set ([i])
        for j in DIFF:   
            B_score += M[i][j]
    return abs(A_score - B_score)



def dfs(depth,member_idx):
    global VISIT,M,N,MIN_SCORE

    # return condition
    if depth == (N//2):
        A = []
        B = []
        for i, v in enumerate(VISIT):
            if v :
                A +=[i]
            else:
                B +=[i]
        score = comparison_team(A,B,M)
        if MIN_SCORE > score:
            MIN_SCORE = score
        return 0

    for i in range(member_idx+1,N):
        VISIT[i] = True
        dfs(depth+1,i)
        VISIT[i]=False
    
    return 0 
            
# backtracking method
def solution2():
    global VISIT,M,N,MIN_SCORE
    M,N = set_test_case()
    VISIT =[False]* N
    MIN_SCORE = 100 
    dfs(0,-1)
    print(MIN_SCORE)


# simple method
def solution():
    # M = score map , N = Soccer member count
    M,N = set_test_case()
    member = [x for x in range(0,N)]

    combi_member = list(itertools.combinations(member,N//2))
    score = 100
    for case in combi_member:
        # two team
        A=[]
        B=[]
        team_bit_map = [False] * N
        
        # Divid team 
        for i in case:
            team_bit_map[i]=True
            A += [i]
        
        for i,v in enumerate(team_bit_map):
            if v == False:
                B += [i]
    
        # score calculate
        local_score = comparison_team(A,B,M)

        if score > local_score :
            score = local_score
    # answer 
    print(score)

def main():
    solution2()
    
if __name__ == '__main__':
    main()

3. 코멘트 

• 총 2가지 방식의 솔루션을 사용했다.
• 첫 번째 방법은 팀 조합(combination)을 library 를 이용하여 구한 뒤, 점수 계산을 했다.
• 함께 스터디한 찬의, 용범님이 백트래킹 방식으로 문제를 해결한 후 리뷰해줘서 같은 방식으로 구현해봤다.
• 두 번째 방법은 팀 조합(combination)을 DFS와 유사한 백트래킹을 이용하여 구한뒤, 점수 계산을 했다.
• 깊이 우선탐색을 경로 탐색 문제를 해결할 때만 떠올렸는데, 조합을 구할때 사용할 수 있다는 것을 또 배웠다.