백준 #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

 

 

---

 

 

백트래킹,,, 아무래도 내가 가장 취약한 부분인 것 같다.

 

for _ in range(c):
    info = [list(map(int, input().split())) for _ in range(11)]
    max_str = 0  # 초기 최댓값
    member = [0] * 11  # 포지션 체크용

    lineup(0, 0)  # 0번 선수부터, 현재까지 능력치 합은 0
    print(max_str)

 

 

우선 메인 코드 부분을 살펴보자.

 

info에서 이중 리스트 형식으로 각 플레이어의 포지션별 능력치를 받아온다.

max_str은 최대 능력치로, 초기값으로 0을 할당해준다.

그 후 백트래킹 함수인 lineup()을 호출한 후, 반환된 값을 출력한다.

 

그럼 백트래킹 함수도 살펴보자.

 

def lineup(num, sums):  # 배치할 선수 인덱스, 현재까지 배치된 선수들의 능력치 합
    global max_str
    if num == 11:
        max_str = max(max_str, sums)  # 최고값 갱신
        return
    
    for i in range(11):
        if member[i] or not info[num][i]:  # 이미 배정된 멤버이거나, 해당 포지션의 능력치가 0
            continue

        member[i] = 1  # 포지션에 배치
        lineup(num + 1, sums + info[num][i])  # 다음 선수 배치 시도
        member[i] = 0  # 원래 상태로 되돌리기

 

 

함수의 매개변수로는 다음 두개가 주어진다.

• num : 현재 배치하려는 선수의 인덱스
• sums : 현재까지 배치된 선수들의 능력치 합

 

max_str 은 전역변수를 사용한다.

 

만일 num이 11이라면, 즉 모든 선수가 배치되었다면 최댓값을 갱신한다.

 

그리고 포지션 0부터 11까지 순회하며, 이미 배치된 포지션이거나, 능력치가 0인 포지션은 제외해야 하므로 continue.

 

유효한 포지션이라면 해당 포지션에 선수를 배치하여 member[i]을 1로 갱신하고,

다음 선수로 넘어가 lineup() 백트래킹을 다시 실행한다.

num + 1번째 선수와 현재까지의 능력치 합 (sums + info[num][i]) 을 매개변수로 전달한다.

 

재귀 호출이 완료된 후에는 member[i]를 0으로 되돌림으로써,

다음 가능한 배치를 시도하기 위해 현재 포지션 i를 다시 사용 가능하도록 한다.

 

---

 

 

완전탐색과 백트래킹의 특징 및 차이점은 뭘까?

 

1. 완전탐색

• 모든 가능한 경우의 수 시도
• 경우의 수가 많으면 시간이 기하급수적으로 증가
• 11! 만큼의 경우의 수 모두 탐색해야 함

 

2. 백트래킹

• 가지치기 통해 불필요한 경로 배제
• 조건 만족하지 않는 경로는 탐색하지 않음
• 시간 효율성 높일 수 있는 방식
• 능력치가 0이거나, 이미 배치된 포지션은 배제