[백준/python] 3980번 선발 명단

1. 문제

 

이 문제는 선수의 능력치를 고려하여 포지션을 정해 가장 최대의 능력치를 구하는 문제이다.

11명의 선수들에 대해 11개 포지션에 대한 능력치를 수치화하여 제시한다.

그 숫자들 중 모든 경우의 수를 고려하여 가장 최대의 합을 구하는 문제이다.

즉, 전형적인 백트래킹 문제.

2. 풀이

솔직히 이 문제를 어떻게 풀어야 할지 감이 안 왔다.

아직 알고리즘 실력이 부족하기 때문인 것 같다.

어떤 상황에서 어떤 알고리즘을 써야 하는지 아직 잘모르는 것 같아서

백트래킹 알고리즘을 다시 정리해야겠다고 생각했다.

https://jemarque.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Backtracking

 

티스토리에 글을 쓰면서 개념 이해가 된 걸 바탕으로 다시 문제에 접근했다.

재귀함수를 활용한 DFS 알고리즘을 적용하여 문제를 해결하기로 했다.

 

일단 능력치 정보를 입력 받고 각 선수에 대한 포지션이 정해졌는지 여부를 checked라는 배열로 만들었다

DFS의 방문처리 역할을 할 배열이다.

능력치 합의 최댓값을 구해야하므로 max_score 변수를 만들고 이걸 global을 사용해 함수 내부에서 사용할 수 있도록 했다.

 

lineup 함수를 만들어 몇 번째 선수의 포지션 정할 차례인지, 현재 점수는 몇 점인지를 인자로 받도록 하였다.

만약 11이 된다면, 즉 11명의 선수 포지션을 모두 정한 뒤라면 최대 합을 갱신하도록 했다.

11번째 선수까지 돌면서 이미 포지션이 있거나 능력치가 0인 경우에는 넘어가고,

그 외의 경우에는 해당 선수번호에 대한 방문처리를 한 후 lineup 함수를 다시 실행하도록 했다.

실행한 함수에 대한 return이 완료되면 방문처리했던 걸 다시 0으로 바꿔주며 재귀함수를 실행한다.

 

처음부터 끝까지 다 돌면서 최대 합을 구해 그 값을 출력하는 방식으로 문제를 해결했다.

3. 코드

def lineup(a, score):
    global max_score
    #11명 다 더한 경우 max_score  갱신 후 return
    if a == 11:
        max_score = max(score, max_score)
        return
    for i in range(11):
        #이미 포지션이 있거나 능력치가 0일 때
        if checked[i] or not stat[a][i]:
            continue
        #방문처리 후 재귀함수 실행 후 방문처리 지우기
        checked[i] = 1
        lineup(a+1, score + stat[a][i])
        checked[i] = 0

c = int(input()) #테스트 케이스
for i in range(c):
    stat = [] #능력치 정보
    checked = [0] * 11 #포지션 정해졌는지 여부
    max_score = 0 #능력치 합 최댓값
    for i in range(11):
        stat.append(list(map(int, input().split())))
    lineup(0, 0)
    print(max_score)

 

4. 결과

 

앞으로도 더 많은 백트래킹 문제를 풀면서 감을 더 익혀야겠다.