[백준] 3980번. 선발 명단(JAVA)

문제

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

---

풀이(21분)

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

public class Main {

    static int c, answer;
    static boolean[] positions;
    static int[][] ability;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        c = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for(int i = 0; i < c; i++){
            positions = new boolean[11]; // 포지션 체크용
            ability = new int[11][11];
            answer = 0;
            for(int j = 0; j < 11; j++){
                st = new StringTokenizer(br.readLine());
                for(int k = 0; k < 11; k++){
                    ability[j][k] = Integer.parseInt(st.nextToken()); // 선수의 포지션 별 능력치
                }
            }

            for(int j = 0; j < 11; j++){
                if(ability[0][j] == 0){
                    continue;
                }
                dfs(0, j, 0);
            }
            System.out.println(answer);
        }




    }

    static void dfs(int player, int position,int count){
        if(player == 10){
            count += ability[player][position];
            answer = Math.max(answer, count);
            return;
        }

        positions[position] = true;
        count += ability[player][position];
        for(int i = 0; i < 11; i++){
            if(positions[i]){ // 이미 포지션이 차있으면 패스
                continue;
            }

            if(ability[player+1][i] == 0){ // 적성에 안 맞으면 패스
                continue;
            }

            dfs(player + 1, i, count);
            positions[i] = false; // 백트래킹
        }
        positions[position] = false; // 백트래킹

    }
}

---

문제 풀이 전략

 

맵의 크기가 정해져있는 단순한 dfs문제이다.

포지션이 차있는지 유무와 적성의 유무를 판단하여 dfs를 진행하면 된다.

과정 중에 체크된 것을 다시 확인하기 위하여 백트래킹도 해줘야한다.