[삼성SW역량][Python/BOJ] 백준 14889 스타트와 링크(DFS, 백트레킹)

 

 

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

14889번: 스타트와 링크

 

 

 

 

# depth은 뽑은 사람의 인원수, idx는 뽑은 사람 다음부터 뽑기위해서 저장

 

 

 

 

 

💻 코드 : 

def dfs(depth, idx) : # depth는 사람의 수
    global min_diff 
    if depth == n//2 :
        power1, power2 = 0,0
        for i in range(n) :
            for j in range(n) :
                if vis[i] and vis[j]  : # i와 j가 동시에 우리팀!
                    power1+= mp[i][j]
                elif not vis[i] and not vis[j] :
                    power2 += mp[i][j]
        min_diff = min(min_diff,abs(power1-power2))
        return 
    for i in range(idx,n) :
        if not vis[i] :
            vis[i] = 1
            dfs(depth+1, i+1 )
            vis[i] = 0 
n = int(input())
mp = [list(map(int,input().split()))for i in range(n)]     
vis = [0] *n 
min_diff = int(1e9)

dfs(0,0)
print(min_diff)

 

 

함수로 빼서 코드를 만들어 보았다. 

def findMin() :
    teamA, teamB = 0,0
    for i in range(n) :
        for j in range(n) :
            if vis[i] and vis[j] :
                teamA += mp[i][j]
            elif not vis[i] and not vis[j] :
                teamB += mp[i][j]
    return abs(teamA - teamB)

# target은 뽑은 사람의 인원수, idx는 뽑은 사람 다음부터 뽑기위해서 저장
def dfs(target, idx) :
    global ans 
    if target == n//2 :
        ans = min(ans,findMin())
        return 
    else :
        for i in range(idx,n) :
            if vis[i] == 0 :
                vis[i] = 1 
                dfs(target+1, i+1 )
                vis[i] = 0
                    
if __name__=="__main__" :
    n = int(input())
    vis = [0]*n
    mp = [list(map(int,input().split())) for _ in range(n)]
    ans = int(1e9)
    dfs(0,0)
    print(ans)

 

 

 

 

 

def dfs(idx, cnt):
    global ans
    if cnt == n // 2:
        print(select)

    for i in range(idx, n):
        if select[i]:
            continue
        select[i] = 1
        dfs(i + 1, cnt + 1)
        select[i] = 0

이렇게 해서 출력하면 

 

 

 

이런식으로 cnt == n//2인 경우가 모두 나온다.

파이썬에서 combination과 같은 결과일것이다. 

 

즉 6개가 있으면 그중 3개를 뽑는 모든 경우를 하는 것이다. 

 

N과 M에서 풀었었던것같은데 이 문제 백트래킹 사용하는 문제였구나 

 

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

 

https://developer-ellen.tistory.com/50?category=879172 

BOJ - 스타트와 링크 14889번 (python)

 

 

복습 :

✅ 20220701

✅  20220915