19년 9월 2주차 : 신에게는 아직 12척의 배가 남았사옵니다

1. 문제 - 난이도 ★

12척의 배가 주어졌을 때, 대장선을 제외한 11척을 이용해 최적의 진형을 찾는 것이다.

 

2. 입력

11 * 11의 행렬이 주어지며, aij는 i번째 배가 진형의 j번째 위치했을 떄의 전투력을 뜻한다.

 

3. 출력

첫번째 줄에 최적의 진형을 이루었을 때의 합을 구한다.

두번째 줄에는 아군의 진형을 첫번째부터 순서대로 출력한다. 최적의 진형이 여러개인 경우 사전순으로 앞선 진형을 출력한다.

 

4. 알고리즘

 문제는 11척의 배를 순서대로 나열할 때, 그 능력치가 최대가 되는 순서를 찾는 문제이다. 가장 간단한 방법은 역시 완전탐색이다. 1번배가 1번자리에, 2번배가 2번자리에, ... , 11번 배가 11번자리에 들어가는 진형부터, 1번배가 11번자리에 2번배가 10번자리에, ..., 11번 배가 1번자리에 들어가는 진형까지 모두 탐색하는 것이다. 이렇게 11개의 배를 나열하는 경우의 수이므로 이것은 11! = 39,916,300가지의 경우의 수가 존재한다.

 

 이 문제를 그림으로 표현하면 다음과 같다.

 반복문 보다는 재귀함수가 효율적으로 풀 수 있다. 아무리 스택이 깊게 들어가더라도 최대 11번이므로 스택 오버플로우는 일어나지 않는다. 

 

 자기 자리를 찾아간 배의 숫자가 11척이 되는 순간을 종료조건으로 설정한다. 또한 한 배가 두 자리에 들어가는 경우를 방지하기 위해 배의 위치를 체크하는 배열을 준비한다. 마지막 문제에서 합이 최대가 될 때의 배의 순서를 요구하고 있으니 해당 순서를 저장할 배열을 생성한다. 배의 위치를 호가인하기 위해 배열을 이용하여 답이 갱신될 때마다 배의 순서 배열도 함께 갱신한다.

 

power = [[0 for _ in range(11)] for _ in range(11)] # i번 배가 j번 자리에 배치될 때 능력치
check = [False] * 11 # i번째 자리에 배가 차지했는지 체크
sel = [0] * 11 # i번째 배가 몇번째 자리에 있는지 저장
ans = float('-inf') # 배의 능력치 총합
seq = [0] * 11 # 정답일 때 배의 순서

def go(s, sum):
    global sel, check, ans, seq
    if s == 11 and ans < sum: # 현재 11번 배에 대해 작업을 수행하고, ans가 sum보다 작다면 갱신
    	ans = sum
        for i in range(11):
            seq[i] = sel[i]
	return
    
    for i in range(11):
    	if check[i] : continue
        check[i] = True
        sel[s] = i + 1
        go(s+1, sum+power[s][i]);
        sel[s] = 0
        check[i] = False

 

5. 코드