SWEA_5209(최소 생산 비용) JAVA(백 트래킹)

문제

SW Expert Academy

다음과 같이 n개의 제품이 n개의 공장에서 생산비용이 정해져 있다. 최소 비용을 구해라.

위의 예시에서는 1 = C, 2 = A, 3 = B 를 하면 최소비용이 된다.

3<=N<=15

 

단순히 순열을 통해 모든 경우의 수를 확인하는 방법이 내가 1번째로 생각한 방법이다.

하지만 N의 범위가 15까지 이므로 최악의 경우 15!의 시간이 걸리므로 시간초과가 발생한다.

 

여기서 백트래킹의 개념이 들어간다.

백트래킹은 정답이 될거같은 것만 탐색하는 것이다.

내가 생각한 방법은 완전탐색이었다.

sol(0, 0, 1);
static void sol(int cnt, int sum, int idx){
        if(cnt == n){
            miin = Math.min(miin,  sum);
            return;
        }
        for(int i=1;i<=n;i++){
            if(route[i] == false){
                if(miin >= sum + arr[idx][i]) { //백트래킹 부분
                    route[i] = true;
                    sol(cnt + 1, sum + arr[idx][i], idx + 1);
                    route[i]=false;
                }
            }
        }
    }

주석으로 처리된 "백트래킹 부분" 이 있어야 완전탐색으로 안하고 백트래킹으로 탐색한다.

즉, 현재 최소값인 miin 보다 작아야지 재귀함수가 동작하는 것이다.

최소값보다 커지면 볼 필요가 없는 것이다.

static void sol(int cnt, int sum, int idx){
        if(cnt == n){
            miin = Math.min(miin,  sum);
            return;
        }
        for(int i=1;i<=n;i++){
            if(route[i] == false){
                route[i] = true;
                sol(cnt+1, sum+arr[idx][i], idx+1);
                route[i]=false;
            }
        }
    }

위 코드는 내가 처음에 작성한 코드이다.

---

전체 코드

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

public class SWEA5209_최소생산비용 {
    static int n;
    static int[][] arr;
    static boolean [] route;
    static int miin = 999999999;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int tc = Integer.parseInt(st.nextToken());
        for(int t = 1;t<=tc;t++){
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            arr = new int[n+1][n+1];

            for(int i=1;i<=n;i++){
                st = new StringTokenizer(br.readLine());
                for(int j=1;j<=n;j++){
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            route = new boolean[n+1];
            sol(0, 0, 1);
            System.out.println("#"+t+" "+miin);
            miin = 999999999;

        }

    }
    static void sol(int cnt, int sum, int idx){
        if(cnt == n){
            miin = Math.min(miin,  sum);
            return;
        }
        for(int i=1;i<=n;i++){
            if(route[i] == false){
                if(miin >= sum + arr[idx][i]) {
                    route[i] = true;
                    sol(cnt + 1, sum + arr[idx][i], idx + 1);
                    route[i]=false;
                }
            }
        }
    }
}