백준 3980[자바] java 선발 명단

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

3980번: 선발 명단

▶문제

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

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

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

이때, 모든 선수의 포지션을 정하는 프로그램을 작성하시오. 모든 포지션에 선수를 배치해야 하고, 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

▶입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 각각의 케이스는 11줄로 이루어져 있고, i번 줄은 0과 100 사이의 11개의 정수 sij를 포함하고 있다. sij는 i번선수가 j번 포지션에서 뛸 때의 능력이다. 모든 선수에게 적합한 포지션의 수는 최대 5개이다. (능력치가 0보다 크다)

▶출력

각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다.

▶해설

입력이 크지 않고 모든 경우의 수를 확인해야 하므로 백트래킹 문제입니다. 조건을 살펴보겠습니다.

 

1. 선수는 최대 5개의 포지션에서 활동할 수 있고, 0인 곳은 활동할 수 없는 곳이다.

2. 최댓값을 구해라.

 

변수들 먼저 설정하겠습니다.

map [][] : 선수들의 포지션 점수판

visit []: 포지션의 남은 자리 (false일 경우 자리가 남아있고, true인 경우 자리가 없음)

 

dfs를 활용하여 백트래킹을 진행합니다. index와 temp을 파라미터로 넘겨주며, index는 0~10까지 사람의 index이고, temp는 그때까지의 값입니다. 따라서 index==11이라면 모든 사람들이 포지션을 가진 것입니다.

이때 포지션의 점수가 0인 곳은 담당할 수 없는 것만 채킹 해주면 됩니다. i는 해당 선수의 포지션 값을 확인하는 변수입니다. 

private static void dfs(int index, int temp){
    if(index==11){
        result = Math.max(temp,result);
        return;
    }

    for(int i=0; i<11; i++){
        if(!visit[i] && map[index][i]!=0){
            visit[i]=true;
            dfs(index+1, map[index][i]+temp);
            visit[i]=false;
        }
    }
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;


public class Main {

    static int t;
    static int[][]map;
    static boolean[]visit;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t= Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<t; i++){
            map = new int[11][11];
            visit = new boolean[11];

            for(int j=0; j<11; j++){
                String[] s = br.readLine().split(" ");
                for(int k=0; k<11; k++){
                    map[j][k] = Integer.parseInt(s[k]);
                }
            }

            dfs(0,0);
            sb.append(result).append("\n");
            result=0;
        }

        System.out.println(sb.toString());
    }

    private static void dfs(int index, int temp){
        if(index==11){
            result = Math.max(temp,result);
            return;
        }

        for(int i=0; i<11; i++){
            if(!visit[i] && map[index][i]!=0){
                visit[i]=true;
                dfs(index+1, map[index][i]+temp);
                visit[i]=false;
            }
        }
    }
}