[코딩테스트][백준] 🔥 백준 14889번 "스타트와 링크" 문제: Python으로 완벽 해결하기!

문제 링크

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

🕒 Python 풀이시간: 30분

최적화 전

from itertools import combinations

n=int(input())
cases=list(combinations(range(0,n),n//2))
alreadys=set()

arr=[]
for _ in range(n):
    arr.append(list(map(int,input().split())))

answer=1e9
for case in cases:
    if case in alreadys:
        continue
    result1=0
    result2=0
    alreadys.add(case)
    alreadys.add(tuple(set(range(0,n))-set(case)))
    for i in range(n):
        for j in range(n):
            if i!=j:
                if i in case and j in case:
                    result1+=arr[i][j]
                elif i not in case and j not in case:
                    result2+=arr[i][j]
    
    answer=min(answer,abs(result1-result2))

print(answer)

최적화 후

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=1e9

def cal_diff(start_team,link_team,arr):
    result1=0
    result2=0
    for i in start_team:
        for j in start_team:
            result1+=arr[i][j]
    for i in link_team:
        for j in link_team:
            result2+=arr[i][j]
    return abs(result1-result2)

def dfs(depth,i,visited,arr,n):
    global ans
    if depth==n//2:
        start_team=[]
        link_team=[]
        for k in range(n):
            if visited[k]:
                start_team.append(k)
            else:
                link_team.append(k)
        diff=cal_diff(start_team,link_team,arr)
        ans=min(diff,ans)
        return
    for k in range(i,n):
        if not visited[k]:
            visited[k]=True
            dfs(depth+1,k+1,visited,arr,n)
            visited[k]=False

visited=[False]*n
dfs(0,0,visited,arr,n)
print(ans)

비트마스크를 활용한 조합 탐색 🧩✨

먼저 생각한 방법은 모든 조합을 구해서 해당 조합의 팀에 따라 점수를 전부 계산하는 방법을 생각하였다. 조합을 구하는데 시간 복잡도가 $2^n$이고 해당 점수를 구하는데 팀당 $n^2$의 시간복잡도가 들기 때문에 $O(2^n*n^2)$가 된다. 하지만 N의 값이 작기 때문에 충분히 가능하다고 생각이 들었다.

라이브러리를 사용하여 간단하게 전체 인원의 반을 전체 인원에서 선발하는 방법으로 팀을 구성하였고 해당 팀을 모두 탐색하지만 조합이기 때문에 결국 겹치므로 이를 또 반으로 줄이기 위해 set를 통해 검사를 시행하였다.

해당 검사가 끝나면 주어진 점수표를 이용해 각 팀의 점수 차를 이중 for문을 통해 검사하므로 결과값이 구해진다.

하지만 비트마스크를 사용한 백트래킹의 방법이 해당 상황에서 불필요한 상황을 계산하지 않기 때문에 더 빠르다고 하여 비트마스크를 사용하여 조합을 구해보았다.

먼저 해당 값이 중복해서 뽑아지면 안되기 때문에 비트마스크의 역할을 할 visited를 선언하였고 전체 인원의 반, 즉 한 팀의 인원이 완성될때까지 for문을 통해 이를 dfs로 반복한다. 그러던 중 우리가 원하던 조건의 인원이 완성되면 답을 구하기 위해 visited를 확인한다.

visited를 통해 한번에 방문한 팀과 방문하지 않은 팀을 N회 for문을 통해 구할 수 있고 이렇게 이루어진 팀을 따로 함수를 두어 점수를 구한다. 이 부분은 다를 것이 없다.

시간복잡도 상으로는 다를 것이 없지만 비트마스크를 이용한 백트래킹이 불필요한 상황을 조건으로 피해가기 때문에 조금 더 빠르다고 한다. 덕분에 백트래킹으로 조합을 구해보는 것을 시도해 볼 수 있었기에 많은 도움이 되었다고 생각한다.

이렇게 Python으로 백준의 "스타트와 링크" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊