이번 문제는 백트레킹을 통해 해결하였다. 가능한 결과값을 백트레킹을 통하여 모두 구한 후에 그 중에서 가장 큰 값을 출력하도록 하였다. 방문 처리는 해당 포지션이 선발된 것과 같은 의미로 사용되었기 때문에 1차원 리스트로 구현하였다. 모든 포지션이 선발되게 되면 idx가 11이 되므로, 이 경우에 결과값을 모아놓는 리스트에 결과값을 담았다.

• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
  -> players를 선언한다.
  -> 11번 반복하며 players를 입력받는다.
  -> 선발 처리에 사용할 리스트 selected를 선언한다.
  -> 결과값을 모아 놓을 리스트 results를 선언한다.
  -> dfs 함수를 idx, total을 인자로 갖도록 선언한다.
  --> 만약 idx가 11일 경우, results에 total을 넣고 함수를 종료한다.
  --> 11번 반복하는 i에 대한 for문을 돌린다.
  ---> 만약 selected[i]가 True일 경우, 다음 반복으로 넘어간다.
  ---> 만약 players[idx][i]가 0이 아닐 경우,
  ----> selected[i]를 True로 갱신한다.
  ----> dfs(idx+1, total+players[idx][i])를 재귀호출한다.
  ----> selected[i]를 False로 갱신한다.
  -> dfs(0, 0)을 호출한다.
  -> results의 최대값을 출력한다.

Code

t=int(input())
for _ in range(t):
    players = []
    for _ in range(11):
        players.append(list(map(int, input().split())))
    selected=[False for _ in range(11)]
    results=[]
    def dfs(idx, total):
        if idx==11:
            results.append(total)
            return
        for i in range(11):
            if selected[i]:
                continue
            if players[idx][i]:
                selected[i] = True
                dfs(idx+1, total+players[idx][i])
                selected[i] = False
    dfs(0, 0)
    print(max(results))