[백준_3980번] 선발 명단

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보다 크다)

 

[코드]

import java.util.*;

public class BaekJoon_3980 {
	static int max;
	static boolean[] visited;
	static int[][] power;
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		int testcase=sc.nextInt();
		
		while(testcase-->0) {
			// 케이스별로 반드시 초기화 해주어야 한다.
			power=new int[11][11];
			visited=new boolean[11];
			max=0;
			
			// 각 선수들의 포시션 별 능력 입력받기
			for(int i=0;i<11;i++) 
				for(int j=0;j<11;j++) 
					power[i][j]=sc.nextInt();
				
			dfs(0,0);
			System.out.println(max);
		}
	}
	
	static void dfs(int depth, int totalscore) {
		// 11명 선수들의 포시션을 모두 선정했다면 최댓값 갱신
		if(depth==11) {
			max=Math.max(totalscore, max);
			return;
		}
		
		// 백트래킹
		for(int i=0;i<11;i++) {
			/*
			 * 아직 선택되지 않은 포지션이고, 해당 포지션에서 선수의 능력이 0이 아니라면
			 * 해당 포시션을 선수에게 할당하고 능력치를 누적한다. 
			 */
			if(!visited[i]&&power[depth][i]!=0) {
				visited[i]=true; 
				dfs(depth+1,totalscore+power[depth][i]);
				visited[i]=false;
			}
		}
	}
}

 

[고찰]

 이번 문제는 백트래킹을 사용해하여 11개의 포지션에 선수들을 할당한 후 능력치의 합이 최댓값이 되는 경우를 찾는 문제이다. 이 부분을 파악하고 처음에는 모든 포지션에 선수들을 한 번씩 할당하게 만들면 되겠지란 생각을 갖고 문제를 풀었지만 시간 초과를 받았다. 그래서 다시 문제를 차근차근 읽어보니 능력치가 0인 포지션에는 해당 선수를 할당할 수 없다는 조건을 빠뜨린것을 확인했다. 

 따라서 포지션에 선수를 배치하는 조건으로 포지션에 아직 선수가 배치되지 않은 것과 동시에 선수의 해당 포지션의 능력치가 0이 아닐때를 추가해주었다. 능력치 조건을 추가하니 시간초과 없이 정답 처리를 받을 수 있었다. 이 조건이 없다면 11개의 포지션에 선수를 배치할 수 있는 모든 경우를 고려해주어야 했기에 정답은 같을지라도 시간초과가 난 것이었다.