[백준]3980: 선발 명단 - JAVA

[백준]3980: 선발 명단

3980번: 선발 명단

풀이

모든 포지션으로 선수를 채웠을때, 능력치의 최댓값을 출력하는 문제로 백트랙킹 유형을 활용하여 문제를 풀었다. 

 

헤당 선수를 뽑았는지 아직 뽑지 않았는지 확인해기 위해 visited 배열을 구현해 주었고, 선수를 뽑을 때마다 능력치의 합을 누적시켜 주었다. 선수를 뽑을때 문제의 조건에 따라 능력치가 0인 선수는 뽑지 않도록 한다. 

 

모든 선수에게 포지션을 지정하는데 성공했다면 pos값이 11이 되었을 것이고, 이때 max값을 현재 total값과 비교하여 지정한 다음 되돌아가 다시 탐색을 진행한다. 

 

모든 탐색이 끝나면 최대 능력치의 값이 max값에 담기게 될 것이고, 이를 출력하여 주면 된다.

코드

import java.util.*;
 
public class Main {
 
    static int[][] position = new int[11][11];
    static boolean[] visited;
    static int max;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int t = scan.nextInt();
        for(int i = 0; i < t; i++) {
            for(int j = 0; j < 11; j++) {
                for(int k = 0; k < 11; k++) {
                    position[j][k] = scan.nextInt();
                }
            }
 
            max = 0;
            visited = new boolean[11];
            backtracking(0, 0);
            System.out.println(max);
        }
    }
 
    public static void backtracking(int pos, int total) {
        if(pos == 11) {
            max = Math.max(max, total);
            return;
        }
 
        for(int i = 0; i < 11; i++) {
            if(!visited[i] && position[pos][i] != 0) {
                visited[i] = true;
                backtracking(pos + 1, total + position[pos][i]);
                visited[i] = false;
            }
        }
    }
}