[백준] 3980 선발 명단 - DFS를 활용한 브루트포스(깊이우선탐색, bruteforce) JAVA

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

3980번: 선발 명단

코드설명

 DFS를 활용한 브루트포스(깊이우선탐색, bruteforce) 문제입니다.

 

모든 경우를 완전탐색해줍니다.

 

유의해야할점은 다음과 같습니다.

1. 선수가 해당 포지션 능력치가 0 이라면 들어가지 못하게 처리합니다. 즉, arr[level][i] > 0 일 경우에만 탐색하도록 처리합니다.

2. 그 포지션을 다른 선수가 사용하기로했다면, 다른 선수는 사용하지 못합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int N, T;
    public static int[][] map;
    public static int[][] arr;
    public static boolean[] positionVisited;
    public static int cnt = 0;
    public static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        T = Integer.parseInt(st.nextToken());
        
        for(int t=0; t<T;t++) {
        	answer = 0;
        	arr = new int[11][11];
        	positionVisited = new boolean[11];
        	for(int i=0;i<11;i++) {
        		st = new StringTokenizer(br.readLine());
        		for(int j=0;j<11;j++) {
        			arr[i][j] = Integer.parseInt(st.nextToken());
        		}
        	}
        	dfs(0, 0);
        	System.out.println(answer);        	
        }
        
    }
    
    public static void dfs(int level, int sum) {
    	if(level == 11) {
    		answer = Math.max(answer,  sum);
    		return ;
    	}
        
    	for(int i=0;i<11;i++) {
    		if(arr[level][i] > 0 && positionVisited[i] == false) {
    			int temp = arr[level][i];
    			positionVisited[i] = true;
    			arr[level][i] = 0;
    			dfs(level + 1, sum + temp);
    			positionVisited[i] = false;
    			arr[level][i] = temp;
    		}
    	}
    	
    }
    

}

 

처음에는 visited[level]. 즉, 해당 선수의 레벨까지 확인했었는데 생각해보면 이전 Level을 다시 체크할 일은 없기에 사용하지않는다.

아래코드보다는 위의 코드로 사용.

    public static void dfs(int level, int sum) {
    	if(level == 11) {
//    		System.out.println("sum:"+sum);
    		answer = Math.max(answer,  sum);
    		return ;
    	}
    	
    	for(int i=0;i<11;i++) {
    		if(visited[level] == false && arr[level][i] > 0 && positionVisited[i] == false) {
    			int temp = arr[level][i];
    			visited[level] = true;
    			positionVisited[i] = true;
    			arr[level][i] = 0;
    			dfs(level + 1, sum + temp);
    			visited[level] = false;
    			positionVisited[i] = false;
    			arr[level][i] = temp;
    		}
    		
    	}
    	
    }