[BOJ] 15686. 치킨 배달 - JAVA 자바

15686번: 치킨 배달

• 228ms
• DFS

치킨가게 중 M개를 선택할 때, 각 집의 치킨 거리 합의 최소값을 구하는 문제이다.

 

치킨가게의 좌표와 집의 좌표만 필요하므로 입력되는 값들을 이차원 배열에 저장하지 않아도 된다. 두 개의 List<int[]> 를 선언하여 치킨가게 좌표와 집의 좌표를 따로 저장해주었다.

 

치킨가게를 포함하는가 포함하지 않는가의 문제로 DFS를 이용하였으며 치킨가게의 포함 여부를 판단하기 위해 boolean[] 배열을 추가로 선언해줬다. M개의 치킨가게를 선택했다면 모든 집과의 치킨 거리를 계산하여 sum에 더해주고 경우에 따른 최소 sum을 찾아준다.

 

#소스코드

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

public class Main {
    static int N, M, min = Integer.MAX_VALUE;
    static boolean[] checked;

    static List<int[]> house = new ArrayList<int[]>();
    static List<int[]> chicken = new ArrayList<int[]>();

    /*
     * 치킨가게 중 M개를 선택할 때, 도시의 치킨 거리의 최소값
     */

    public static void dfs(int index, int count) {
        if (count == M) {
            // 치킨거리 구하기
            int sum = 0;
            for (int i = 0; i < house.size(); i++) {
                int minDist = Integer.MAX_VALUE;

                for (int j = 0; j < chicken.size(); j++) {
                    if (checked[j]) {
                        int dist = Math.abs(chicken.get(j)[0] - house.get(i)[0])
                                + Math.abs(chicken.get(j)[1] - house.get(i)[1]);
                        minDist = Math.min(dist, minDist);
                    }
                }
                sum += minDist;
            }

            min = Math.min(sum, min);
            return;
        }

        if (index >= chicken.size())
            return;

        // index 번째 치킨 집 포함
        checked[index] = true;
        dfs(index + 1, count + 1);

        // index 번째 치킨 집 미포함
        checked[index] = false;
        dfs(index + 1, count);
    }

    public static void main(String[] args) throws NumberFormatException, 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 tmp = Integer.parseInt(st.nextToken());

                if (tmp == 1)
                    house.add(new int[] { i, j });
                else if (tmp == 2)
                    chicken.add(new int[] { i, j });
            }
        }

        checked = new boolean[chicken.size()];

        dfs(0, 0);

        System.out.println(min);
    }
}