[백준] 16439 치킨치킨치킨 - 완전탐색(DFS) JAVA

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

16439번: 치킨치킨치킨

문제풀이

1. DFS 로 치킨의 3개의 조합을 구합니다. (visited[] 로 방문처리하면서 조합과 함꼐 구합니다. )

2. 고른 치킨의 3개 중에서 회원이 가장 좋아하는 치킨의 만족도를 구합니다 (bestChicken 으로 한 사람당 최고의 치킨만족도를 구합니다.)

3. 회원 모두의 최대 치킨 만족도를 구한 값의 만족도를 answer에 넣고서 Math.max로 최대값을 구합니다.

 

DFS를 통하여 치킨의 조합을 구할때 1 2 3 4 5 의 치킨이 있다고 가정하면, (1 2 3), (1 3 2) 의 치킨 조합은 같은것과 마찬가지이니 순열로 구하는것이 아닌 조합으로 구해야합니다. 그렇기 위해서 idx를 사용하여 이미 지나간 조합은 더이상 건들지 않게 합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {	
	public static int N, M;
	public static int[][] chicken;
	public static boolean[] visited;
	public static int answer = 0;
	public static int result = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken()); // 아이스크림 종류
    	M = Integer.parseInt(st.nextToken()); // 섞어먹으면 안되는 조합의 개수
    	chicken = new int[N][M];
    	visited = new boolean[M];

    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			chicken[i][j] = Integer.parseInt(st.nextToken());	
    		}
    	}
    	
    	simulate(0, 0);
    	System.out.println(answer);
	}
    
    public static void simulate(int idx, int level) {
    	if(level == 3) {
    		result = 0;
    		for(int i=0;i<N;i++) {
    			int bestChicken = 0;
    			for(int j=0;j<M;j++) {
    				if(visited[j] == true) {
    					bestChicken = Math.max(bestChicken, chicken[i][j]);
    				}
    			}
    			result += bestChicken;
    		}
    		answer = Math.max(answer,  result);
    		return ;
    	}
    	
    	for(int i=idx;i<M;i++) {
    		if(visited[i] == true) continue;
    		visited[i] = true;
    		simulate(i + 1, level + 1);
    		visited[i] = false;
    	}
    	
    }
    
    
    
}