[백준] 15686번 치킨 배달

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

15686번: 치킨 배달

---

해당 문제에선 너무 많은 배열 변수들과 for문을 덮어써서 시간 초과날 줄 알았지만, 특별히 문제가 없었다.

 

내가 생각한 풀이 방법이다.

 

1. 맵 정보를 입력받을 때, 집과 치킨집의 좌표 정보를 담은 배열을 저장한다.
   1. 집( value = 1) : home.add
   2. 치킨집(value = 2) : chicken.add
2. 모든 집-치킨집 사이의 거리를 구한다.
   1. 2차원 배열 dist를 생성해서 dist[치킨집인덱스][집인덱스]로 거리를 계산하여 입력한다.
3. 치킨집 중 M개를 뽑는다.
   1. 전체 치킨집 수(=chicken.size()) 중 M개를 뽑기 위해 조합을 사용한다.
   2. combination()의 파라미터로 index_size, result, start, depth를 입력받는다.
      1. int index_size : 실제로 chicken.size()로, 각 치킨집마다 인덱스 번호가 있기에 인덱스로 조합을 구현하기 위해 index_size가 필요하다. 만약 인덱스 번호처럼 '0 ~chiken.size()-1 ' 과 같은 단위가 아닌 주어진 배열의 값들로 조합을 해야한다면 int arr[] 같은 파라미터를 넣으면 된다.
      2. int result[] : 조합의 결과를 담은 배열이다. 만약 5개 중 3개의 치킨집을 골라야한다면 result는 {1,2,3} 과 같은 값이 담길 수 있다. 
      3. int start : 탐색을 시작할 인덱스 정보이다. 탐색은 0부터 시작하며, 한번의 탐색을 끝날 때마다 +1을 하여, 그 다음 인덱스부터 탐색하도록 한다.
      4. int depth : 탐색의 depth 정보이다. depth도 한번의 재귀를 할 때마다 +1이 되며, 보통 depth가 특정한 value에 도달하면 종료되도록 하여 무한하게 탐색하는 것을 막는다.
   3. 조합을 통해 나온 조합을 토대로 , 각 조합별로 최소거리를 구해 result_dist[]에 담는다.
      1. 나온 조합만큼 (=comb.size()) 반복문을 반복하여
      2. 해당 조합에서 최소거리를 구한다.
      3. result_dist에 담는다. 
   4. result_dist를 오름차순 정렬하여, result_dist[0]을 출력한다. 

++ ) combination할 때, 기존에는 result를 그대로 comb.add(result) 했는데, 이럴 경우 result 배열의 변경이 comb ArrayList에 영향을 미친다.

예를 들어 result 값으로 {1,2,3}이 저장되어 있고 종료 조건이 되어 comb.add(result) 했는데, 이 후 탐색에서 result가 {1,2,4}로 변경됐을 경우 기존의 add된 result가 함께 {1,2,4}가 되는 것이다. 즉 주소 참조를 하기 때문에 배열이 제대로 저장되지 않는다.

해결을 위해, 종료 조건까지 도달한 result를 새로운 배열로 복사하여 저장한다.

 

package yejin.song;

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

public class BOJ_치킨배달 {
    static int N;
    static int M;
    static ArrayList<int[]> home;
    static ArrayList<int[]> chicken;
    static ArrayList<int[]> comb;

    static int[][] dist;

    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());
        home = new ArrayList<>();
        chicken = new ArrayList<>();
        comb = new ArrayList<>();


        // 1(집)의 배열 따로 담기
        // 2(치킨집)의 배열 따로 담기
        for (int i = 0 ; i<N; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j< N; j++){
                int value = Integer.parseInt(st.nextToken());
                // 0이면 반복문 탈출하도록
                if (1 == value) {
                    home.add(new int[]{i,j});
                }
                else if (2 == value){
                    chicken.add(new int[]{i,j});
                }
            }
        }

        // 모든 치킨집-집 거리 구하기
        dist = new int[chicken.size()][home.size()];
        for (int i = 0; i< chicken.size(); i++){
            for (int j = 0; j< home.size(); j++){

                int chic[] = chicken.get(i);
                int hom[] = home.get(j);

                int sero = Math.abs(chic[0] - hom[0]);
                int garo= Math.abs(chic[1] - hom[1]);

                dist[i][j] = sero + garo;
            }
        }

        // 치킨집 인덱스 기준으로 M개 뽑기 (조합)
        int[] result = new int[M];
        combination(chicken.size(), result,0,0);

        // 각 조합별 최소거리 결과 담을 배열
        int result_dist[] = new int[comb.size()];

        // comb.size()만큼 돌면서 최소 거리 구하기
        for (int i = 0; i< comb.size(); i++){
            int pick[] = comb.get(i);
            int min_dist[] = new int[home.size()];
            Arrays.fill(min_dist, 100); //큰 수로 초기화

            // 각 집 인덱스 (0,...) 별로 dist 돌아가며 비교
            for (int z = 0 ; z< home.size(); z++){
                for(int j = 0; j< pick.length; j++){
                    int index = pick[j];
                    int dist_value = dist[index][z];
                    min_dist[z] = Math.min(min_dist[z], dist_value);
                }
            }
            result_dist[i] = Arrays.stream(min_dist).sum();
        }

        // 각 조합 별로 구한 최소 거리를 오름차순 정렬 -> 즉, 최종적인 최소 거리 구함.
        Arrays.sort(result_dist);

        System.out.println(result_dist[0]);
    }

    static void combination(int index_size, int[] result, int start, int depth){
        // 종료 조건
        if (depth == result.length){
            int[] copy = Arrays.copyOf(result, result.length);
            comb.add(copy);
            return;
        }

        for (int i = start; i < index_size ; i++){ // 인덱스만큼 반복하기
            result[depth] = i;
            combination(index_size, result, i+1, depth+1);
        }
    }
}

 

+) 4달 후 다시 푸는 ing

package yejin.song;


import java.util.*;
import java.io.*;

public class codingTest {

    static int N,M;
    static ArrayList<int[]> home = new ArrayList<>();
    static ArrayList<int[]> chicken = new ArrayList<>();
    static ArrayList<int[]> comb_list = new ArrayList<>();

    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()); // 치킨집 몇개 살릴건지


        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j =0 ; j < N; j++){
                int num = Integer.parseInt(st.nextToken());

                // 값이 1 혹은 2이면 list에 위치 정보 add
                if (num == 1) home.add(new int[]{i,j});
                if (num == 2) chicken.add(new int[]{i,j});
            }
        }

        // 모든 집-치킨집의 거리 구하기
        int dist[][] = new int[home.size()][chicken.size()];

        for (int i = 0; i < home.size(); i++){
            for (int j = 0; j < chicken.size(); j++){
                int home_arr[] = home.get(i);
                int chicken_arr[] = chicken.get(j);
                dist[i][j] = Math.abs(home_arr[0]- chicken_arr[0]) +  Math.abs(home_arr[1]- chicken_arr[1]);
            }
        }


        // M개를 고르는 경우의 수 구하기 (combination) -> DFS
        int arr[] = new int[M]; // 조합 정보 계속 저장할 배열임.

        dfs(0,0, arr);

        int min_dist = 999999; //최종 리턴할 변수

        for (int comb[] : comb_list){ // 각 조합별 최소거리 구하기
            int sum_min_dist = 0;
            for (int i = 0 ; i< home.size(); i++){ // 각 집별로 최소거리 구하기
                int home_min_dist = 999999;
                for (int value : comb){
                    home_min_dist = Math.min(home_min_dist, dist[i][value]);
                }
                sum_min_dist += home_min_dist;
            }
            min_dist = Math.min(min_dist, sum_min_dist);
        }

        System.out.println(min_dist);
    }

    public static void dfs(int start, int depth, int arr[]){
        if (depth == M) {
            int copy[] = Arrays.copyOf(arr, M);
            comb_list.add(copy);
            return;
        }
        for (int i = start; i < chicken.size(); i++){
            arr[depth] = i;
            dfs(i+1, depth+1,arr);
        }

    }


}