[백준] BOJ 3980 선발 명단 (골드 5)

문제

---

https://www.acmicpc.net/problem/3980

3980: 선발 명단

---

해설

---

1. 처음엔 최대값을 찾기 위해서는 모든 순열을 만들어보아야 한다고 판단하여 넥퍼를 사용하였지만 시간 초과
   
   • 넥퍼를 사용할 때 만들어진 순열의 합을 더할 때 0을 더해야 하는 경우를 스킵하려고 했지만 (나름의 백트래킹)
     넥퍼를 통해 모든 순열을 만드는 과정에서 시간이 오래 걸렸기 때문에 시간안에 들어오지 못한 것 같다!
2. 따라서, 0일때 해당 경우를 스킵하고 다른 경우를 찾을 수 있도록 백트래킹으로 문제 해결
   
   
3. 입력을 받아 이를 바탕으로 백트래킹 수행
   
   
4. 이미 다른 선수가 해당 포지션에 선택된 경우
   or 현재 포지션을 선택할 선수가 해당 포지션에 능력치가 0인 경우 다음 경우의 수 확인
   
   
5. 최종적으로 11명의 선수 모두 포지션을 가진 상태라면 최대값을 갱신한다.

---

코드 (백트래킹)

---

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

public class BOJ3980 {
    static final int ELEVEN = 11;
    static int[][] positions;
    static boolean[] isv;
    static int max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            positions = new int[ELEVEN][ELEVEN];
            isv = new boolean[ELEVEN];
            for (int j = 0; j < ELEVEN; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int k = 0; k < ELEVEN; k++) {
                    positions[j][k] = Integer.parseInt(st.nextToken());
                }
            }
            max = 0;
            backtracking(0, 0);
            sb.append(max).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static void backtracking(int depth, int sum) {
        if (depth == ELEVEN) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < ELEVEN; i++) {
            if(positions[depth][i] == 0 || isv[i]) continue;
            isv[i] = true;
            backtracking(depth + 1, sum + positions[depth][i]);
            isv[i] = false;
        }
    }
}

---

결론

---

예전에는 백트래킹을 어려워했는데 이제는 수월하게 구현해낼 수 있게 성장한 것 같아서 뿌듯하다. ฅ(՞៸៸> ᗜ < ៸៸՞)ฅ

---