[알고리즘] SWEA 요리사 - 자바

 

[풀이 코드]

package day0214;

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

public class SWEA_요리사 {
	static int TC;
	static int N;
	static int[][] array;
	static int min = Integer.MAX_VALUE;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		TC = stoi(br.readLine());
		for(int tc=1; tc<=TC; tc++) {
			N = stoi(br.readLine());
			array = new int[N][N];
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					array[i][j] = stoi(st.nextToken());
				}
			}
			min = Integer.MAX_VALUE;
			visited = new boolean[N];
			dfs(0, 0);
			System.out.printf("#%d %d \n",tc, min);
		}
	}
	
	
	static void dfs(int idx, int cnt) {
		if(cnt == N/2) {
			int ans = diff(); // ans : 두 요리의 차이
			min = Math.min(min, ans); // 제일 적은 두 요리의 차이 리턴
			return;
		}
		if(idx>=N)
			return;
		
		visited[idx]=true;
		dfs(idx+1, cnt+1);
		visited[idx]=false;
		dfs(idx+1, cnt);
					
	}
	
	static int diff() {
		int aSum =0; // a요리
		int bSum =0; // b요리
		
		for(int i=0;i<N-1;i++) { // 나눠진 식재료를 가지고 a요리, b요리 만들기
            for(int j=i+1;j<N;j++) {
                if(visited[i] && visited[j]) aSum+=array[i][j]+array[j][i]; 
                else if(!visited[i] && !visited[j]) bSum+=array[i][j]+array[j][i];
            }
        }

		return Math.abs(aSum - bSum); // 두 요리의 차이
	}
	
	static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

• 로직은 맞았으나 예제 입력 8번부터 10번까지 답이 이상하게 나왔다. 도대체 뭐가 문제인 건지 헤매다가 기존에는 재귀 함수를 아래와 같이 작성했다.
  
  
• diff() 함수에서는 나누어진 식재료를 가지고 이중 for문을 돌면서 요리를 만드는 과정이다. 이 과정을 생각하는 것 또한 오래 걸렸다.  애초에 방문 배열을 썼으면 쉽게 풀렸을걸..

 

[이전 코드]

static void dfs(int idx, int cnt, String str) {
		if(cnt == N/2) {
			int ans = diff(str); // ans : 두 요리의 차이
			min = Math.min(min, ans); // 제일 적은 두 요리의 차이 리턴
			return;
		}
		if(idx>=N)
			return;
		
		dfs(idx+1, cnt+1, str+idx);
		dfs(idx+1, cnt, str);
	}
    
static int diff() {
    int aSum =0; // a요리
    int bSum =0; // b요리

    boolean[] visited = new boolean[N];
    for(int i=0; i<str.length(); i++){
        visited[str.charAt(i)-'0'] = true; 
    }
        
    for(int i=0;i<N-1;i++) { // 나눠진 식재료를 가지고 a요리, b요리 만들기
        for(int j=i+1;j<N;j++) {
            if(visited[i] && visited[j]) aSum+=array[i][j]+array[j][i]; 
            else if(!visited[i] && !visited[j]) bSum+=array[i][j]+array[j][i];
        }
    }

    return Math.abs(aSum - bSum); // 두 요리의 차이
}

• 애초에 dfs(0, 0, "")로 시작해서 idx값을 str에 누적해주는 식으로 했다. 아직까지는 위의 코드의 문제점을 찾지 못했고 추측되는 이유는 str에 들어가지 못한 idx값이 있을 것이라는 것과 String객체를 계속 전달하면서 생길 수 있는 문제가 있는 것..?
  
  
• 아무튼 이것 때문에 시간 다 날렸다... 간단하게 풀려고 하다가 오히려 시간이 더 걸린 문제ㅜ