dfs를 통해 문제를 해결할 수 있었다
dfs의 인자로 인덱스와 현재 sum 값을 설정하고 처음에는 dfs(0,0)으로 함수를 호출했다
함수 안에서는 graph를 하나씩 방문해주며, 방문하지 않았을 경우 방문처리를 해주고 인덱스+1과 현재 sum에 graph 값을 더한 것을 시작점으로 dfs를 재귀적으로 호출하였다
idx가 11이 됐을 경우, result를 최댓값으로 갱신해주었다
소스 코드
import sys
input = sys.stdin.readline
def dfs(idx, now):
global result
if idx == 11:
result = max(result, now)
return
for j in range(11):
if visit[j]: continue
if graph[idx][j]:
visit[j] = 1
dfs(idx+1, now + graph[idx][j])
visit[j] = 0
T = int(input())
for _ in range(T):
graph = [list(map(int, input().split())) for _ in range(11)]
result = 0
visit = [0] * 11
dfs(0, 0)
print(result)