백준 3980 (선발 명단) java

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

3980번: 선발 명단

import java.io.*;
import java.util.*;
public class Main {
    static int[][] board = new int[11][11];
    static boolean[] isIn = new boolean[11];
    static int[] value = new int[11];
    static int result = 0;
    static int num = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        num = Integer.parseInt(br.readLine());
        int[] rarr = new int[num];
        for(int k=0;k<num;k++) {
            for (int i = 0; i < 11; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < 11; j++) {
                    board[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            travel(0, 0);
            rarr[k]=result;
            result = 0;
        }
        for(int i=0;i<num;i++)
        {
            System.out.println(rarr[i]);
        }
        br.close();
    }

    static void travel(int k,int v)
    {
        if(k==11)
        {
            if(result<v)
            {
                result = v;
            }

            return;
        }

        for(int i=0;i<11;i++)
        {
            if(board[k][i]!=0)
            {
                if(!isIn[i])
                {
                    isIn[i]=true;
                    travel(k+1,v+board[k][i]);
                    isIn[i]=false;
                }

            }
        }
    }
}

생각보다 간단한 문제이다. 만약 해당 자리에 선수가 이미 배정이 되었는데 더 큰 점수를 가진 선수가 나오면 바꿔주는 작업을 해줘야 하는게 아닌가?? 라는 생각을 처음에 했다. 하지만 백트랙킹의 정의에 대해 다시 한번 생각해보자. 백트랙킹은 기본적으로 가능한 모든 경우의 수를 재귀적으로 작업하는 것이다!!

 

isIn[i] 를 true 에서 false로 바꿔주는 작업만 해줘도 모든 경우의 수 , 더 큰 자리의 선수가 나오는 경우도 계산이 가능하다는 것이다 !