[ baekjoon ] 선발 명단 3980번 ( python )

문제

백준 3980 선발 명단 풀이 ( 파이썬 )

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

3980번: 선발 명단

 

풀이

단순하게 백트래킹을 이용해서 문제를 풀었다.

visited는 해당 선수를 썼는지 안썼는지를 나타낸다.

n=int(input())
ans=0
def dfs(pos,visited,deep,hap):
    global ans
    if deep==11:
        ans=max(ans,hap)
        # print(ans)
        return
    for i in pos[deep]:
        score,po,pe=i
        if po==deep and not visited[pe]:
            visited[pe]=True
            dfs(pos,visited,deep+1,hap+score)
            visited[pe]=False
    return
    
while True:
    ans=0
    pos=[[] for _ in range(11)]
    
    arr=[]
    visited=[False]*11
    for i in range(11):
        arr.append(list(map(int,input().split())))
        for j in range(11):
            if arr[i][j]!=0:
                pos[j].append((arr[i][j],j,i))
    # print(pos)
    dfs(pos,visited,0,0)
    print(ans)
    n-=1
    if n==0:
        break