[백준 3980 🥇] 선발 명단

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

3980번: 선발 명단

문제

챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다.

오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다.

수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100까지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.

이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오. 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 각각의 케이스는 11줄로 이루어져 있고, i번 줄은 0과 100사이의 11개의 정수 sij를 포함하고 있다. sij는 i번선수가 j번 포지션에서 뛸 때의 능력이다. 모든 선수에게 적합한 포지션의 수는 최대 5개이다. (능력치가 0보다 크다)

출력

각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다.

문제 풀이

import sys

t=int(sys.stdin.readline())

# idx : idx번째 포지션에 올 선수 저장
# total : 총 능력치
def DFS(idx, total):
    global maxans
    if idx == 11:
        maxans = max(maxans, total)
        return

    for p in range(11):
        # 이미 포지션에 배치된 선수이거나 선수가 해당 포지션의 능력치가 0인 경우, 다음 선수 탐색
        if visited[p] == 1 or player[p][idx] == 0:
            continue
        visited[p] = 1
        total += player[p][idx]
        DFS(idx + 1, total)
        total -= player[p][idx]
        visited[p] = 0

for _ in range(t):
    player=[]
    # input
    for i in range(11):
        power=list(map(int, sys.stdin.readline().split(' ')))
        player.append(power)
    visited=[0]*(11)
    maxans=0
    DFS(0,0)
    print(maxans)

https://1eehyunji.tistory.com/entry/%EB%B0%B1%EC%A4%80-3967-%F0%9F%A5%87-%EB%A7%A4%EC%A7%81-%EC%8A%A4%ED%83%80

[백준 3967 🥇] 매직 스타

• 위 문제와 비슷하게 DFS를 이용한 완전 탐색 사용해서 풀었다!
• DFS(idx, total) : idx번째 포지션에 어떤 선수가 올지 탐색하는 DFS이고, total은 이전 포지션에 오는 선수들을 계산해서 나온 현재까지의 총 능력치를 의미한다. 
• 각 idx별로 DFS를 돌면서 아직 포지션이 배정되지 않았고(visited[p]==0), 해당 포지션의 능력치가 0 이상(player[p][idx]>0)인 선수를 idx번 포지션에 배정하고, (visitied[p]=1, total+=player[p][idx]) DFS 탐색 후에 해당 DFS가 탐색이 종료되면 다시 선택해제(visited[p]=0, total-=player[p][idx])해준다.
• 이와 같은 DFS 탐색 과정에서 idx가 11이 되면, 즉 모든 포지션에 각 선수들을 배정하면 total 값과 maxans 값을 비교하여 최댓값을 갱신한다.