[BOJ] 14889번 스타트와 링크 / 사용언어 : 파이썬(python)

※ 문제링크

14889번: 스타트와 링크

※ 관련 알고리즘 설명

[알고리즘] 백트래킹(Backtracking)이란? (feat. DFS, 기준함수, sum of subset)

 

해당문제는 DFS와 백트래킹을 활용하여 푸는 문제였다. 문제를 해결하기 위해 처음 떠올린 풀이방법은 아래와 같았다.

1. 입력받은 값들을 N//2의 갯수를 가진 조합식 구하기(6개를 입력받으면 3개로 만들 수 있는 모든 조합들 구하기)

2. 조합식들을 다시 2개의 조합으로 짤 수 있는 모든 조합을 구해서 배열에서 값 추출 후 합 구하기

3. 각각의 합들의 차의 절댓값을 구해서 최솟값 산출하기

풀이방법을 생각하는 것은 그리 어렵지 않았으나, 역시나 시간초과가 문제였다. 처음 풀때는 각각의 풀이들을 다 나누어 짠 후 합치는 형식으로 진행했는데 그러다 보니 시간과 메모리가 너무 많이 들어 시간초과가 나왔다. 처음 짰던 코드는 아래와 같다.

 

# 실패사례 - 개념은 맞았으나 시간초과
N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
num_list = [x for x in range(N)]
check_list = [False] * N
com = []
r_list1 = []
# 팀으로 나눠질 수 있는 경우의 수 추출
def dfs(start): 
    if len(com) == N//2:
        r_list1.append(com.copy())
        return
    
    for i in range(start, N):
        if check_list[i]:
            continue

        check_list[i] = True
        com.append(num_list[i])
        
        dfs(i)

        com.pop()
        check_list[i] = False
dfs(0)

# 팀으로 가질수 있는 경우의 수 중 2개의 팀으로 만들어질 수 있는 쌍 찾기
r_list2 = [] 
num1, num2 = 0, 0
while True:
    if num1 == len(r_list1) - 1 and num2 == len(r_list1) - 1:
        break 
    elif num2 == len(r_list1) - 1:
        num1 += 1
        num2 = 0
    else:
        cnt = 0
        for value in r_list1[num1]:
            if value in r_list1[num2]:
                break
            else:
                cnt += 1
            if cnt == N // 2:
                r_list2.append([r_list1[num1], r_list1[num2]])
    num2 += 1

# 팀 속에서 나올 수 있는 조합 및 조합에 따른 숫자추출 후 합 구하기
def dfs_plus(sample):
    global score
    if len(com) == 2:
        # ch_list.append(com.copy())
        ch_list.append(arr[com[0]][com[1]])
        return ch_list
    
    for i in range(N // 2):
        if check_list_plus[i]:
            continue

        com.append(sample[i])
        check_list_plus[i] = True

        dfs_plus(sample)

        com.pop()
        check_list_plus[i] = False

for i in range(len(r_list2)):
    for k in range(2):
        sample = r_list2[i][k]
        check_list_plus = [False] * (N // 2)
        com = []
        ch_list = []
        dfs_plus(sample)
        r_list2[i][k] = sum(ch_list)
value = abs(r_list2[0][0] - r_list2[0][1]) 

# 두 팀의 능력치 차이 비교후 최솟값 찾기 
for i in range(1, len(r_list2)):
    if value > abs(r_list2[i][0] - r_list2[i][1]):
        value = abs(r_list2[i][0] - r_list2[i][1])
print(value)

 

시간을 줄일 방법을 생각하던 중 방문기록을 기준으로 백트래킹을 하고 있었기에, 하나의 출력값이 나올때 True로 나온 값은 start팀으로 False값을 가지는 변수들은 link팀으로 부여해주는 방식으로 수정하면 시간을 줄일 수 있다고 생각하여 해당방식으로 수정을 해보았고, 그 결과 PyPy3로만 통과가 가능한 코드가 만들어졌다. 해당 코드는 아래와 같다.

 

# Pypy3로만 통과가능
N = int(input())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
num_list = [x for x in range(N)]
check_list = [False] * N
start_T = []
link_T = []
r_list = []
def dfs(start): # 숫자 조합 만들기
    global link_T
    if len(start_T) == N//2:
        for num in num_list:
            if num not in start_T: # True는 start팀으로 Fasle는 link팀으로
                link_T.append(num)   
        r_list.append([start_T.copy(), link_T.copy()])
        link_T = []
        return
    
    for i in range(start, N):
        if check_list[i]:
            continue

        check_list[i] = True
        start_T.append(num_list[i])
        
        dfs(i)

        start_T.pop()
        check_list[i] = False
dfs(0)

def dfs_plus(sample):
    global score
    if len(com) == 2:
        ch_list.append(arr[com[0]][com[1]])
        return ch_list
    
    for i in range(N // 2):
        if check_list_plus[i]:
            continue

        com.append(sample[i])
        check_list_plus[i] = True

        dfs_plus(sample)

        com.pop()
        check_list_plus[i] = False

for i in range(len(r_list)//2):  # 절반까지만 보면됨.
    for k in range(2):
        sample = r_list[i][k]
        check_list_plus = [False] * (N // 2)
        com = []
        ch_list = []
        dfs_plus(sample)
        r_list[i][k] = sum(ch_list)
        
value = abs(r_list[0][0] - r_list[0][1]) 
for i in range(1, len(r_list)//2):  # 절반까지만 보면됨.
    if value == 0:
        break
    if value > abs(r_list[i][0] - r_list[i][1]):
        value = abs(r_list[i][0] - r_list[i][1])
print(value)

 

그 후로는 추가적인 시간 단축방법이 떠오르지 않아 구글링을 통해 다른 사람들의 코드를 참고하여 방법을 확인해봤고,  다양한 방법으로 해결한 방법들을 보며 추가적인 학습을 해보았다. 참고했던 사이트들은 구글링을 하면 따로 링크를 걸지 않았다.

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.