[백준, Java] 3980번, 선발 명단(완전 탐색, 백트래킹)

문제 링크

3980번: 선발 명단

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. C개의 테스트 케이스를 진행합니다.

2. 11개의 포지션과 11명의 선수가 존재하며 각 포지션의 능력치를 갖고 있습니다.

3. 능력치가 0이면 해당 포지션이 될 수 없습니다.

4. 11명의 포지션에 선수가 배정된 경우 능력치의 합의 최대값을 결과로 출력합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 포지션의 선수가 배정되는 방법을 탐색합니다.

 

3. 팀이 완성된 경우의 능력치 합 최대값을 출력합니다.

 

팀을 만들자(완전 탐색, 백트래킹)

 

팀을 만드는 과정은 완전 탐색을 통해 진행할 것입니다.

 

각 포지션마다 배정 가능한 선수를 배정한 뒤, 다음 포지션의 선수들을 순차적으로 배정하며, 선수들을 각 포지션에 배정할 수 있는 방법을 탐색합니다.

▶︎ 완전 탐색

 

하지만, 여기서 능력치가 0인 선수는 포지션에 배정할 수 없으므로, 현재 배정할 포지션에 선수들이 모두 0이면 해당 포지션에는 선수를 배정할 수 없습니다.

▶︎ 백트래킹

 

또한, 현재 선수가 포지션에 배정된 선수라면 다른 포지션에는 배정하지 못하기 때문에 비트마스킹을 통해서 사용 여부를 확인하였습니다.

 

00000000000 : 아무도 포지션에 배정되지 않은 상태

 

00000000001 : 1번째 선수만 포지션의 배정된 상태

 

00000000101 : 1, 3번째 선수만 포지션의 배정된 상태

 

이와 같이 비트마스킹을 통해서 각 선수가 포지션에 배정되었는지 확인합니다.

 

위 3가지 방법을 조합하여 만들 수 있는 팀의 능력치 최대값을 탐색합니다.

 

※ 예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

예제입력 1.

1. 입력된 정보를 저장합니다.

 

11명의 선수 정보

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

 

2. 각 포지션의 선수가 배정되는 방법을 탐색합니다.

 

포지션 1 : 배정할 수 있는 선수 - [ 1번 선수 ]

 

포지션 2 : 배정할 수 있는 선수 - [2, 3, 4, 5, 7번 선수]

 

...

 

팀 배정 성공 예시

포지션 1 : 1번 선수

 

포지션 2 : 2번 선수

 

...

 

포지션 11 : 11번 선수

 

모든 포지션 선수 배정 성공 = 능력치의 합 : 970

 

팀 배정 실패 예시

 

포지션 1 : 1번 선수

 

포지션 2 : 2번 선수

 

...

 

포지션 9 : 10번 선수

 

포지션 10 : 배정할 선수 X....

 

팀 생성 실패!

 

 

3. 팀이 완성된 경우의 능력치 합 최대값을 출력합니다.

 

탐색을 통해 얻은 능력치 합의 최대값 : 970

 

970을 결과로 출력합니다.

 

 

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 통해 선수 정보를 띄어쓰기 기준 나누었습니다.
• C개의 테스트 케이스에 대해서 팀 생성 방법 search 함수를 통해서 탐색합니다.
• 탐색마다 얻은 능력치 합의 최대값을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

결과코드

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

public class Main {
  static final int FULL_MASK = 2047;
  public static void main(String[] args) throws IOException {
    //입력값 처리하는 BufferedReader
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //결과값 출력하는 BufferedWriter
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    //테스트 케이스
    int c = Integer.parseInt(br.readLine());
    StringTokenizer st;
    //각 테스트 케이스 진행
    for(int tc = 1; tc<=c;tc++){
      int[][] player = new int[11][11];
      //선수단 정보 저장
      for(int i=0;i<11;i++){
        st = new StringTokenizer(br.readLine());
        for(int j=0;j<11;j++){
          player[i][j] = Integer.parseInt(st.nextToken());
        }
      }
      //탐색하여 팀을 이루는 최대 능력치 값 구하기.
      int answer = search(0, 0, 0, player);
      //능력치 합 최대값 BufferedWriter 저장
      bw.write(String.valueOf(answer));
      bw.newLine();
    }
    bw.flush();		//결과 출력
    bw.close();
    br.close();
  }
  //재귀와 비트마스킹을 이용하여 선수들의 포지션을 배정하는 방법을 탐색 및 최대값 구하는 함수
  public static int search(int pos, int mask, int score,  int[][] player){
    //모든 포지션에 선수가 배정된 경우
    if(pos == 11){
      return score;
    }
    int maxScore = -1;
    //현재 포지션에 배정할 선수 탐색
    for(int i=0;i<11;i++){
      //해당 선수가 포지션에 배정하지 못한 경우
      if(player[i][pos] == 0){
        continue;
      }
      //현재 선수 마스킹 값
      int curMask = 1 << i;
      //먼저 포지션에 배정되지 않은 선수라면 배정후 다음 포지션 선수 탐색
      if((mask & curMask) == 0){
        maxScore = Math.max(search(pos+1, mask ^ curMask, score + player[i][pos], player ), maxScore);
      }
    }
    //최대값 반환
    return maxScore;
  }
}