[백준] 3980 : 선발 명단

https://www.acmicpc.net/problem/3980

3980번: 선발 명단

---

• 선수는 11명 고정이지만, 하나의 포지션당 최대 5명 선수들까지밖에 들어가지 않는다.
• 따라서 가능한 경우의 수는 5^6 * 5! 가지가 되므로, 모든 경우의 수를 탐색하더라도 시간이 충분하다.
• 하나의 테스트케이스를 수행하기 위해 선수들을 백트래킹을 통해 각 포지션별로 뽑아주고, 테케마다 정답을 초기화시켜줘야 다음 테케에 영향을 미치지 않는다.

---

C = int(input())
answer = 0

# idx 번째 포지션에 적합한 선수를 고르고, 다음 포지션을 재귀적으로 탐색
def select(idx, mat, pos, visit, value):
    # 모든 선수들을 다 고를 수 있는 경우에만 최대값 갱신
    if idx == 11:
        global answer
        if value > answer:
            answer = value
        return
    # 해당 포지션에 적합한 모든 선수들을 탐색하는데
    for candidate in pos[idx]:
        # 이미 앞에서 다른 포지션에 선택된 선수는 제외시키고
        if visit[candidate]: continue
        visit[candidate] = True
        # value 에 해당 선수의 해당 포지션 능력치를 더해주면서 다음 포지션 재귀호출
        select(idx+1, mat, pos, visit, value+mat[candidate][idx])
        visit[candidate] = False

# 각 테스트케이스에 대해
for _ in range(C):
    mat = [list(map(int, input().split())) for r in range(11)]
    # 각 포지션에 적합한 선수들의 목록을 관리(0번 포지션에 적합한 선수들, ...)
    pos = [[] for i in range(11)]
    for i, player in enumerate(mat):
        for idx, val in enumerate(player):
            if val != 0:
                pos[idx].append(i)
    # 포지션을 차례대로 선택해나가는 백트래킹 과정
    select(0, mat, pos, [False for i in range(11)], 0)
    print(answer)
    # 테케가 여러개이기 때문에 정답 값 초기화 필요
    answer = 0