3980: 선발 명단

문제 링크

3980: 선발 명단

구현 방식

• 전형적인 backtracking 문제
• 최댓값 갱신 조건: depth == 11
• check = [False]*11를 통해 해당 포지션에 배치가 됐는 지 안됐는 지를 판별해주었다
• not check[i] and S[depth][i] != 0인 경우에 backtracking 방식으로 재귀 호출

코드

import sys

def dfs(depth, path):
    global max_score

    if depth == 11:
        max_score = max(max_score, sum(path))
        return
    
    for i in range(11):
        if not check[i] and S[depth][i] != 0:
            check[i] = True
            dfs(depth+1, path + [S[depth][i]])
            check[i] = False


C = int(sys.stdin.readline()[:-1])
for c in range(C):
    S = []
    for _ in range(11): S.append(list(map(int, sys.stdin.readline()[:-1].split())))
    
    max_score = 0
    check = [False]*11
    dfs(0, [])
    print(max_score)