[백준/파이썬] #3980

백트래킹이라는 힌트를 얻어서 풀어서 초반의 접근은 쉬웠다. 테스트 케이스는 맞았으나, 문제는 틀렸다. 

import sys

sys.setrecursionlimit(10**7)

def solution(array):
    global answer

    def backtrack(count, current_sum):
        global answer
        if count >= 11:
            answer = max(answer, current_sum)
            return
        
        for i in range(11):
            if array[count][i] == 0:
                continue
            backtrack(count+1, current_sum + array[count][i])
            

    backtrack(0, 0)
    return answer

if __name__ == "__main__":
    T = int(input())
    arr = None
    for _ in range(T):
        arr = []
        answer = 0
        for _ in range(11):
            arr.append(list(map(int, input().split())))
        print(solution(arr))

 

참고한 풀이를 보니 접근은 비슷했다. 다만 '해당 선수의 포지션이 정해졌는지'를 표시해주는 부분이 빠졌었다. 이 부분만 추가해 주었더니 잘 통과했다. 

import sys

sys.setrecursionlimit(10**7)

def solution(array):
    global answer
    global checked	# 추가한 부분

    def backtrack(count, current_sum):
        global answer
        global checked	# 추가한 부분
        if count >= 11:
            answer = max(answer, current_sum)
            return
        
        for i in range(11):
            if array[count][i] == 0 or checked[i]:
                continue
            checked[i] = True	# 추가한 부분
            backtrack(count+1, current_sum + array[count][i])
            checked[i] = False	# 추가한 부분
            

    backtrack(0, 0)
    return answer

if __name__ == "__main__":
    T = int(input())
    arr = None
    answer = None
    checked = None	# 추가한 부분
    for _ in range(T):
        arr = []
        checked = [False] * 11	# 추가한 부분
        answer = 0
        for _ in range(11):
            arr.append(list(map(int, input().split())))
        print(solution(arr))