[BOJ][🟡5][백준#03980] 선발 명단

문제 출처

BAEKJOON Online Judge #3980

문제

챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다. 오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다. 수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100까지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다. 이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오. 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

입력

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

출력

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

예제

입력

1
100 0 0 0 0 0 0 0 0 0 0
0 80 70 70 60 0 0 0 0 0 0
0 40 90 90 40 0 0 0 0 0 0
0 40 85 85 33 0 0 0 0 0 0
0 70 60 60 85 0 0 0 0 0 0
0 0 0 0 0 95 70 60 60 0 0
0 45 0 0 0 80 90 50 70 0 0
0 0 0 0 0 40 90 90 40 70 0
0 0 0 0 0 0 50 70 85 50 0
0 0 0 0 0 0 66 60 0 80 80
0 0 0 0 0 0 50 50 0 90 88

출력

970

My Sol

import sys; input = sys.stdin.readline

def calc(pos):
    global visited_pos, visited_per
    global pools, max_score, total

    if pos==11:
        if sum(visited_pos)==11 and max_score < total:
            max_score = total
        return

    # 해당 포지션을 담당할 사람이 있다면 다음 포지션
    if visited_pos[pos]:
        calc(pos+1)

    else:
        pool = pools[pos]
        for per, score in pool:
            if not visited_per[per]:
                visited_per[per] = 1
                visited_pos[pos] = 1
                total += score
                calc(pos+1)
                visited_per[per] = 0
                visited_pos[pos] = 0
                total -= score


T = int(input())
for _ in range(T):

    # mat 정의
    mat = [list(map(int, input().split())) for _ in range(11)]

    # pools 정의
    pools = [[] for _ in range(11)]
    for per, lst in enumerate(mat):
        for pos, score in enumerate(lst):
            if score:
                pools[pos].append((per, score))

    # 해당 포지션 가능한 유일한 사람 찾아 채우기
    visited_pos = [0]*11
    visited_per = [0]*11
    total = 0
    max_score = 0
    for pos in range(11):
        if len(pools[pos]) == 1:
            per, score = pools[pos][0]
            visited_per[per] = 1
            visited_pos[pos] = 1
            total += score

    calc(0)
    print(max_score)

입력 처리와 변수

여러 조합과 재귀함수로 문제를 해결할 수 있었다. 우선 입력으로 들어오는 선수(per)들의 포지션(pos)과 각 포지션의 점수(score)을 mat 2차원 배열에 처리하여 정의한다. 그리고 이 각각에서 선수, 포지션, 점수 정보를 담는 pools 2차원 배열을 만든다.

mat은 각 행이 person, 각 열이 position이므로, mat을 enumerate하여 각 행, per마다 lst를 받았고, 그 내부에 lst를 다시 enumerate하여 pos와 score 점수로 정의하였다. 그리고 score가 0이 아니라면 해당 pos와 per, score을 pools[pos]의 리스트 내에 (per, score) tuple로 저장한다.

대체 불가능한 포지션 선별

먼저 대체 불가능한 사람들을 포지션에 채워야 한다. 한 포지션에 대한 여러 후보가 있는 경우에만 depth를 늘려가며 확인하면 되는 일이기 때문에 0부터 10까지의 수에 대하여 pools[pos]가 1인 포지션을 찾는다. pools[pos]는 곧, 해당 포지션을 소화할 수 있는 선수들의 번호와 능력치이기 때문이고, 이것이 1이라는 것은 한 사람만 해당 포지션을 소화할 수 있다는 말이다.

재귀함수 내에서 판별을 위한 visited_per과 visited_pos를 11개의 0이 있는 리스트로 초기화하고, 이를 per과 pos를 인덱스로 하여 각각 1로 체크해준다. 후에 이것이 1이라면 이 자리에 후보를 넣지 않고 지나칠 것이다.

그리고 총점인 total에 score을 넣어주면 한 포지션에 한 선수만 가능한 경우에 대한 초기 계산을 마칠 수 있다.

calc 함수 1: 종료조건

PS를 위한 함수이므로 냅다 전역변수를 쓰기 위해 global을 때려넣었다. 전달인자는 pos로, 0부터 시작해 계산하며 10까지의 계산을 지나 11에 다다르면 되돌아가야 한다. 이때 sum(visited_pos)==11, 즉 모든 포지션에 선수가 위치하고, 현재까지 최고점수보다 지금의 배치가 더 큰 누적점수를 가진다면 이를 최고점수로 갱신하고 되돌아간다.

calc 함수 2: 해당 포지션에 사람이 있다면?

해당 포지션에 선수가 있다면 for문을 돌 필요도 없이 다음 pos로 넘어가주면 되겠다.

calc 함수 3: 재귀 조건 정의

pools의 pos인덱스의 리스트를 pool로 둔다. 이 pool의 항목은 tuple들인데, 각각이 해당 pos에서 가용한 선수들의 번호인 per과 score의 쌍으로 이루어진다. 이전 과정에서 선수를 사용했다면 visited_per[per]==1일 것이고, 이런 경우 다음 tuple로 넘어가야 한다. 이를 위한 조건문을 걸고, visited_per[per]이 0인 경우에 하위 코드를 진행한다.

처음으로 만난 visited_per[per]==0인 per과 score에 대하여 해당 per을 pos에 사용한다고 가정해보자. 그러면 visited는 per과 pos에 대하여 모두 1로 체크해주고, 누적 점수인 total에 score을 더해 다음 pos로 넘어가면 되겠다.

모든 pos를 찍어 max_score와 total을 비교해 갱신하고 돌아오면 visited를 0으로 체크해제하고 total에서 score을 빼준 뒤 다음 pool에 대하여 또 조회를 진행한다.

결과

맞았습니다!!

모범답안

출처

from sys import stdin

T = int(stdin.readline())

ans = 0
def solve(idx,count):
    if idx == 11:
        global ans
        ans = max(ans,count)
        return

    for i in range(11):
        if players[idx][i]!= 0 and not visit[i]:
            visit[i]=True
            solve(idx+1,count+players[idx][i])
            visit[i]=False


for _ in range(T):
    ans = 0
    players = [list(map(int,stdin.readline().split())) for _ in range(11)]
    visit = [False]*11
    solve(0,0)
    print(ans)

길이가 짧으면서도 연산속도가 좋았던 문제 풀이를 참고한다.

나는 초반에 포지션을 혼자 소화할 수 있는 사람을 선별해서 제거하였기 때문에 visited에 대해서 per과 pos가 모두 필요했는데, 이 분의 풀이는 per에 대해서만 조회한다. 왜냐하면 pos의 의미인 idx는 0부터 시작해서 10까지 순차적으로 진행되기 때문이다. 때문에 선수에 대한 visit만 체크하기 때문에 간결하다.

또한 나는 0은 제외하고 score가 있는 칸의 pos와 per을 tuple로 해서 리스트에 별도로 담고 이 각각만 조회했는데, 이 분은 무차별적으로 0부터 10까지 모든 depth에서 조회해서 ‘0이면 말고’ 하는 브루트포스 방식을 사용하였다. 때문에 코드가 간결하였다. 이것이 무작정 좋다기엔 내 풀이의 연산 시간이 약 7~8% 정도 더 빨랐는데, depth가 깊어질수록 이러한 무차별 검색 방식에 대한 연산 시간 증가가 영향을 줄 것으로 보인다.

그리고 알고리즘 풀이에만 갇혀서 생각하지 못했는데 max(a, b) 함수를 사용해서 depth가 11인 경우에 손쉽게 비교해서 갱신하였다. 왜 max함수 생각을 못했지ㅋㅋ