[백준/JAVA] BOJ 3980 - 선발 명단

백트래킹,, 도르마무 도르마무,,

👀 문제

3980번: 선발 명단 ✨ 골드 5

챔피언스 리그 결승전을 앞두고 있는 맨체스터 유나이티드의 명장 퍼거슨 감독은 이번 경기에 4-4-2 다이아몬드 전술을 사용하려고 한다.

오늘 결승전에 뛸 선발 선수 11명은 미리 골라두었지만, 어떤 선수를 어느 포지션에 배치해야 할지 아직 결정하지 못했다.

수석코치 마이크 펠란은 11명의 선수가 각각의 포지션에서의 능력을 0부터 100까지의 정수로 수치화 했다. 0은 그 선수가 그 포지션에 적합하지 않다는 뜻이다.

이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오. 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 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

🔑 키포인트

백트래킹

✍️ 코드

📍 각 선수는 능력치가 0인 포지션에 배치될 수 없으므로, 수열을 만들 때 이 조건을 추가해 경우의 수를 줄여 시간을 줄여줘야 한다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ3980_선발명단 {
    static int[][] power;
    static boolean[] visited;
    static ArrayList<Integer> perm;
    static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int t = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < t; tc++) {
            power = new int[11][11];
            visited = new boolean[11];

            for (int i = 0; i < 11; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 11; j++) {
                    power[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            answer = 0;
            perm = new ArrayList<>();
            permu(0);
            sb.append(answer + "\n");
        }
        System.out.print(sb.toString());
    }

    static void permu(int depth) {
        if (depth == 11) {
            int hab = 0;
            for (int i = 0; i < perm.size(); i++) {
                hab += power[i][perm.get(i)];
            }
            answer = Math.max(answer, hab);
            return;
        }
        for (int i = 0; i < 11; i++) {
            if (!visited[i] && power[perm.size()][i] != 0) {
                visited[i] = true;
                perm.add(i);
                permu(depth + 1);
                visited[i] = false;
                perm.remove(perm.size() - 1);
            }
        }
    }
}