[백준] 3980 선발명단

www.acmicpc.net/problem/3980

3980번: 선발 명단

for tc in range(int(input())):
    player = [0] * 11
    for i in range(11):
        player[i] = list(map(int,input().split()))
    visit = [0] * 11
    max_val = 0
    def comb(index=0, total=0):
        if index == 11:
            global max_val
            if max_val < total:
                max_val = total
        else:
            for i in range(11):
                if not player[i][index] or visit[i] == 1: continue
                visit[i] = 1
                comb(index+1, total+player[i][index])
                visit[i] = 0

    comb()
    print(max_val)

모든 조합을 구하는 문제인데,  조건을 주어서 빠져나오는 백트래킹을 사용하면 된다.

모든 조합을 만들면서 조건을 주어서 빠져나오는 것만 하면 백트래킹인지는 모르겠다.