백준 3980번: 선발 명단

백준 3980번: 선발 명단

백트래킹 문제이다. 어제 풀었던 넴모넴모와 비슷한 유형이라 비슷한 방식으로 풀이했다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
C=int(input())
def dfs(x, position, res):
    global ans
    if x==11:
        return
    if position==11:
        ans = max(ans, res)
        return
    dfs(x+1, position, res) #이번 선수는 해당 포지션에 선택하지 않음
    if(tc[x][position]!=0 and visited[x]==0):
        visited[x]=1
        dfs(0, position+1, res+tc[x][position]) #이번 선수를 해당 포지션에 선택함
        visited[x]=0

for _ in range(C):
    ans = 0
    visited=[0 for _ in range(11)]
    tc = [list(map(int,input().split())) for _ in range(11)]
    dfs(0,0,0)
    print(ans)

각 포지션에서 각 선수를 선택하지 않는 경우와, 각 선수가 능력치가 0이 아니고, 이미 선택되지 않았을 경우 선택하는 경우 두개로 나누어서 dfs를 수행하도록 했다. 처음에 ans=0을 맨 위에 뒀다가 틀렸다고 나왔는데, 테스트 케이스별로 수행하니 ans는 for문 내부에 둬서 매번 초기화시켜줘야한다.