[BOJ] 백준 15686 - 치킨 배달 (자바)

백트래킹 (순열(?)),,,,...,

2018년 상반기 CE/IM 2번 문제..   DS보단 문제가 쉬웠던 듯 하다..

삼성 SW테스트는 참 백트래킹을 좋아하는 듯하다..

풀이

1. 치킨집과 집을 각각 Person List , Chichken List에 저장해준다. (나는 ArrayList를 사용함)

2. 치킨집들 중에 M개를 선택해야한다.

00000 부터 11111 까지 계산후 1의 갯수가 M개 일때 계산을 할 수 있지만, 그러면 시간초과가 날 듯 싶어 백트래킹을 이용하여 풀었다.

정확히 M개일때 그 이상으로 넘어가지 않도록 return 해주면 시간이 단축된다.

예를 들어) 치킨집 5개중 3개를 선택해야하는 경우 치킨집 1, 2, 3, 4, 5 가 존재한다.

이때, (1 2 3), (1 2 4), (1 2 5), (2 3 4), (2 3 5), (3 4 5)  의 경우의 수가 생긴다.

경우의 수를 만드는 것은 코드를 통해 확인하길...

3. 경우의 수를 만들었다면 미리 저장해놨던 Person을 선택된 Chicken 집에 각각 거리를 비교해서 최단 거리를 찾는다.

4. 경우의 수마다 모든 최단 거리를 찾아 최단 거리들 중 가장 짧은 최단 거리를 비교하여 찾아내면 된다.

소스

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
class Main {
    static int N;
    static int M;
    static int[][] arr;
    static ArrayList<Dot> chicken;
    static ArrayList<Dot> person;
    static int[] output;
    static boolean[] visited;
    static int result;
 
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        arr = new int[N][N];
        result = Integer.MAX_VALUE;
        chicken = new ArrayList<Dot>();
        person = new ArrayList<Dot>();
 
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
                if (arr[i][j] == 1) {
                    //1일때는 사람 list에 추가
                    person.add(new Dot(i, j));
                } else if (arr[i][j] == 2) {
                    //2일때는 치킨 list에 추가
                    chicken.add(new Dot(i, j));
                }
            }
        }
        //-------입력부-------//
        
        //치킨 집 선택을 위한 배열 visited, output
        visited = new boolean[chicken.size()];
        output = new int[chicken.size()];
        
        //치킨 집 선택
        for (int i = 0; i < chicken.size(); i++) {
            visited[i] = true;
            ChickenSelection(i, 0);
            visited[i] = false;
        }
        System.out.println(result);
    }
    
    //치킨집 선택을 위한 함수
    public static void ChickenSelection(int start, int depth) {
        output[depth] = start + 1;
        
        for (int i = start; i < chicken.size(); i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            ChickenSelection(i, depth + 1);
            visited[i] = false;
        }
        //치킨집이 선택되었을 경우
        //(치킨집이 최대 M개 이므로 depth은 M-1 이 되어야한다. 0부터 시작했으니깐)
        if (depth == M - 1) {
            int sum = 0;
            int currentM = 0;
            //사람이 갈수 있는 치킨집의 경우중 가장 최소값을 선택한다.
            //person 한명씩 모든 Chicken 집을 선택하여 최소값을 비교한다.
            for (int i = 0; i < person.size(); i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < M; j++) {
                    currentM = Calc(person.get(i), chicken.get(output[j] - 1));
                    min = Math.min(min, currentM);
                }
                //최소값일 경우 더한다.
                sum = sum + min;
            }
            //치킨집 경우의 수마다 다른 최소거리중 가장 작은 최소거리를 선택한다.
            result = Math.min(result, sum);
        }
    }
    
    //위치 거리 계산 함수
    public static int Calc(Dot d1, Dot d2) {
        return Math.abs(d1.x - d2.x) + Math.abs(d1.y - d2.y);
    }
}
 
class Dot {
    int x;
    int y;
 
    Dot(int x, int y) {
        this.x = x;
        this.y = y;
    }
}