[백준] 14889번 스타트와 링크 - 파이썬

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

14889번: 스타트와 링크

n = int(input())

team_point= [ ]

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

def dfs(idx):
    global minans

    if idx == n //2:
        start_team =0
        link_team = 0
        for i in range(0,n):
            if i not in start:
                link.append(i)
        for i in range(0,n//2-1):
            for j in range(i+1,n//2):
                start_team += team_point[start[i]][start[j]]+team_point[start[j]][start[i]]
                link_team +=team_point[link[i]][link[j]]+team_point[link[j]][link[i]]
        diff =abs(start_team-link_team)

        if minans >diff:
            minans =diff
        link.clear()
        return

    for i in range(n):
        if i in start:
            continue
        if len(start) >0 and start[len(start)-1] > i:
            continue
        start.append(i)
        dfs(idx +1)
        start.pop()

minans = float('Inf')
dfs(0)
print(minans)

https://kyun2da.github.io/2020/08/11/startandlink/

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

이문제는 진짜 이분꺼 참고 했다

진짜 어럅다..

 

1. 이 문제는 푸는 순서 우선 입력으로 n 과 팀의 시너지가 들어온다.

2. dfs 를 진행하면서 start 팀과 link 팀을 나눈다. 이과정은 밑에 있는 for 문에서 진행한다. 

for 문에서 start에 i 가 있으면 그냥 넘어가고 없으면 start의 길이가 0보다 크고 start의 배열의 길이의 

-1 인덱스에 있는 숫자가 i 보다 크면 넘어간다. <- 이부분이 어려울수 있다 잘 생각해보자.

 

3.여기서 위에 두 조건을 둘다 만족하지 못하면 start에 i 를 추가한다.

처음 시작할때는 위에 두조건을 만족하지 못하므로 무조건 0을 start 에 추가한다.

4. 여기가 핵심인 dfs 의 재귀 함수의 핵심이다.

dfs 함수에 들어가면서 우선 인덱스의 값을 확인하고 n을 반으로 나눈 값의 조건을 따진다.

 

5. 4. 의 조건이 맞지 않다면 밑에 for 문으로 가서 다시 추가 한다.

6. start팀의 조건이 충족 된다면  이제 드디어 팀간의 시너지를 계산 한다. 

여기서 이제 start에 없는 팀원의 숫자를 link에 넣는다. 

 

7. link 팀과 스타트 팀에 있는 값을 팀 시너지로 계산하고 끝나면 link 팀을 비운다.

 

8. 비운 link 팀과 start 팀에서 하나를 빼고 나머지 값을 반복하면서 다음 숫자를 넣는다.

 

아무틈 계속 반복하면서 가장 차이가 작은 숫자를 갱신해준다.

 

어려운 문제였다 실버 수준이지만 이부분에서 많은 사람들이 알고림즘 학습에 

멈추지 않을 까...

 

import sys

n = int(sys.stdin.readline())
graph = []
for _ in range(n):
    graph.append(list(map(int,sys.stdin.readline().split())))

min_gap = 1000000
visited = [False] * n
def dfs(idx,depth):
    global min_gap
    if depth == n//2:
        start_team = 0
        link_team = 0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j] :
                    start_team += graph[i][j]
                elif not visited[i] and not visited[j]:
                    link_team += graph[i][j] 
        gap = abs(start_team-link_team)
        if gap <= min_gap:
            min_gap = gap
        return
    for i in range(idx,n):
        if not visited[i]:
            visited[i] = True
            dfs(i+1,depth+1)
            visited[i] = False

dfs(0,0)
print(min_gap)

오랜만에 다시 감을 잡기위해 풀어보았다 

그사이에 실력도 많이 늘었고 이문제를 다시 보았을 때 

엄청 어렵게는 느껴지지 않았다

 

백트래킹을 풀때는 몇가기 주의점만 고려하면된다.

1. 재귀함수 중단 조건 백트래킹을 마무리할때 어떻게 할건지

2. 위에 중단 조건으로 마무리 되고나고 다른 방식을 찾을 때 방문을 취소하는 법

 

이거 두개만 지키면 해결 가능하다.