[BOJ] 3980. 선발 명단(Python) / DFS, Backtracking

3980번: 선발 명단

11개의 포지션에 11명의 선수를 채웠을 때, 능력치의 합의 최댓값을 구하는 문제.

# 42분 소요. (한 번에 통과, PyPy3 제출 기준 시간 1위 달성했다!) 

• 사용 알고리즘 : Backtracking, DFS 순열 구하기
• 무난하게 순열 구하는 dfs 재귀로 접근해 가지치기하여 가짓 수를 쳐냈다. 
• 원래 dfs 순열로는 11개 자리에 11명을 각각 다른 자리에 배치하는 경우의 수가 39,916,800개가 나오는데, Backtracking으로 가지치기하면 경우의 수가 1824개로 확연히 준다.
• perm 함수에서 0~10 위치별로 돌리며 이미 다른 선수가 포지션을 차지했거나, 이 자리에서 해당 선수가 부적합하다면 continue해서 이로부터 파생될 수 있는 모든 가짓 수를 쳐낸다.(가지치기)
• 해당 포지션에 해당 선수가 올 수 있다면 방문 체크 해주고, 현재 점수에 낼 수 있는 점수를 더하며 다음 재귀(다음 player 탐색)로 보낸다.
• 11명의 선수가 모두 배치되면, 그 때의 score와 전역변수 max_score의 최댓값으로 갱신한다.

 

백트래킹에 대한 설명은 여기에 잘 정리해뒀다. 참고하길!

[Algorithm] 백트래킹(Backtracking)이란?

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

# 나의 풀이(176ms/123752kb)
def perm(player, score):
    global max_score
    if player == 11:
        # print(order, score)
        max_score = max(max_score, score)   # 최대 점수 갱신
        return
    for i in range(11):
        if visited[i] or not stats[player][i]:   # 가지치기. 해당 포지션에서 적합하지 않으면 넘기기 
            continue
        visited[i] = 1      # 방문 가능
        order[player] = i
        perm(player+1, score+stats[player][i])
        order[player] = -1
        visited[i] = 0

# main
T = int(input())
for _ in range(T):
    stats = [list(map(int, input().split())) for _ in range(11)]
    max_score = 0
    order = [0] * 11		# 포지션별 선수 배치
    visited = [0] * 11		# 방문 체크용
    perm(0, 0)
    print(max_score)

---

• 시간 : 176ms / 메모리 : 123752kb(PyPy3 제출)
• 고찰 : Gold 4라기엔 많이 쉬웠다. 체감상 실버 1정도..? 내 생각에 백준 N과 M(1) 문제만 수월하게 풀 수 있다면 아주 무난하게 맞았으리라 생각한다. Backtracking에 취약하니까 문제 더 많이 풀어보자!