1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/3980

(1) 조건 분석 📊

2차원 배열로 11명의 선수의 포지션 별 능력치가 주어진다.
- 만약 members(i)(j) = k 라면, i번 선수의 j 포지션 능력치는 k라는 뜻이다.
- 만약 members(i)(j) = 0 라면, i번 선수는 j 포지션에서 뛸 수 없다.
11명의 선수를 포지션에 잘 배치해서 능력치 합계의 최대치를 출력하라.

2. 코드가 나오기까지 🛠️

KEY WORD: 순열, 백트래킹

순열로 포지션 별 선수 뽑기
1. 이때 현재 조회 중인 선수가 해당 포지션에서 뛸 능력이 없다면 넘어감 -> 백트래킹
base-case에서 선수들의 포지션별 능력치 합계를 낸다.
최대치를 갱신한다.

(1) 시간복잡도 분석 ⏳

11! = 41,896,800 이라서 1억을 안 넘어서 괜찮을 거 같다.
또한 도중에 백트래킹 요소를 넣었기에 실제 계산 경우의 수는 더 줄어들 것이다.

3. 코드 🌐

(1) SUDO CODE 💬

의사 코드는 위의 설명과 같아서 생략한다.

(2) JAVA CODE ☕

import java.util.*;
import java.io.*;

public class Main {
    static int answer = 0;
    static int [][] members;
    static boolean [] isVisited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int TC = Integer.parseInt(br.readLine());

        for(int t = 0; t < TC; t++){
            members = new int [11][11];
            for(int i = 0; i < 11; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int j = 0; j < 11; j++){
                    members[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            isVisited = new boolean [11];
            permutation(0, new int [11]);
            System.out.println(answer);
            answer=0;
        }
    }
    // members의 행 = 선수 번호, 열은 포지션
    // answer의 index = 선수 번호, answer의 value = 포지션
    // isVisited의 index = 포지션, value = 포지션 썼는지 아닌지
    public static void permutation(int depth, int [] position) {
        // base-case
        if(depth == 11) {
            int sum = 0;
            for(int i = 0; i < 11; i++){
                sum += members[i][position[i]];
            }
            answer = Math.max(answer, sum);
            return;
        }

        for(int i = 0; i < 11; i++) {
            if(isVisited[i]) continue;
            if(members[depth][i] == 0) continue;

            isVisited[i] = true;
            position[depth] = i;
            permutation(depth+1, position);
            isVisited[i] = false;
        }
    }
}