[백준] 2961 도영이가 만든 맛있는 음식 - 완전탐색 (DFS) JAVA

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

2961번: 도영이가 만든 맛있는 음식

코드설명

일반적인 완전탐색 문제로, DFS를 통하여 만들 수 있는 음식의 조합을 구한다음에 신맛과 쓴맛의 차이점을 구하면 됩니다.

 

처음에 계속해서 틀려서 어떤이유인지 확인결과 level > 1 초과로 코딩을 해놓아서 올바르게 나오지 않았습니다.

    	if( level >= 1) {
    		result = Math.min(result,  Math.abs(sourTaste - hurtTaste));
    	}

또 처음에 제가 작성한 코드처럼 조합을 구해서 진행하는방식이 아닌 다른방식도 같이 작성해보았습니다.

 

 

코드

조합을 통해 결과를 구함

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

public class Main {
	
	public static String T;
	public static int N;
	public static Node[] Node;
	public static boolean[] visited;
	public static long result = Integer.MAX_VALUE;
    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());
    	Node = new Node[N];
    	visited = new boolean[N];
    	
    	for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		Node[i] = new Node(a, b);
    	}	
    	simulate(0, 1, 0, 0);
    	System.out.println(result);
    }
    
    public static void simulate(int idx, long sourTaste, int hurtTaste, int level) {
    	if(level == N) {
    		result = Math.min(result,  Math.abs(sourTaste - hurtTaste));
    		return ;
    	}
    	if( level >= 1) {
    		result = Math.min(result,  Math.abs(sourTaste - hurtTaste));
    	}
    	for(int i=idx;i<N;i++) {
    		if(visited[i] == true) continue;
    		Node temp = Node[i];
    		int sourTasteTemp = temp.sourTaste;
    		int hurtTasteTemp = temp.hurtTaste;
    		visited[i] = true;
    		simulate(i + 1, sourTaste * sourTasteTemp , hurtTaste + hurtTasteTemp, level + 1);
    		visited[i] = false;
    	}
    }
   
}

class Node{
	int sourTaste; //신맛
	int hurtTaste; //쓴맛
	public Node(int sourTaste, int hurtTaste) {
		this.sourTaste = sourTaste;
		this.hurtTaste = hurtTaste;
	}
}

 

 

DFS 분기처리를 통해 구함( 조합을 구한것과 마찬가지자만 방향이 살짝 다르다. )

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

public class Main {
	
	public static String T;
	public static int N;
	public static Node[] Node;
	public static boolean[] visited;
	public static long result = Integer.MAX_VALUE;
    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());
    	Node = new Node[N];
    	visited = new boolean[N];
    	
    	for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		Node[i] = new Node(a, b);
    	}	
    	simulate(0);
    	System.out.println(result);
    }
    
    public static void simulate(int level) {
    	if(level == N) {
    		int sour = 1;
    		int hurt = 0;
    		for(int i=0;i<N;i++) {
    			if(visited[i] == true) {
    				sour *= Node[i].sourTaste;
    				hurt += Node[i].hurtTaste;
    			}
    		}
    		if(sour!= 1 && hurt != 0) result = Math.min(result,  Math.abs(sour - hurt));
    		return ;
    	}
    	
    	visited[level] = true;
    	simulate(level + 1);
    	visited[level] = false;
    	simulate(level + 1);

    }
   
}

class Node{
	int sourTaste; //신맛
	int hurtTaste; //쓴맛
	public Node(int sourTaste, int hurtTaste) {
		this.sourTaste = sourTaste;
		this.hurtTaste = hurtTaste;
	}
}

 

 

정답코드3입니다. 가장 짧은 코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, H, W, K, M;
	public static int answer = 0;
	public static int[][] food;
	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());
		food = new int[N][2];
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			food[i][0] = a;
			food[i][1] = b;
		}
		System.out.println(bruteforce(0, 0, 0));
		
	}
	
	public static long bruteforce(int depth, int now, int visited) {
		if(depth == N) {
			return calculate(visited);
		}
		
		long ret = Long.MAX_VALUE;
		ret = bruteforce(depth + 1, now + 1, visited + (1 << now));
		ret = Math.min(ret, bruteforce(depth + 1, now + 1, visited));
		
		return ret;
	}
	
	public static long calculate(int visited) {
		boolean isContainsZeroFood = true;
		
		long aTaste = 1, bTaste = 0; 
		for(int i=0; i<N; i++) {
			if( (visited & (1<<i)) > 0) {
				isContainsZeroFood = false;
				aTaste *= food[i][0];
				bTaste += food[i][1];
			}
		}
		if(isContainsZeroFood) return Long.MAX_VALUE;
		return Math.abs(aTaste - bTaste);
	}
	
}