[99클럽 5기 코테 스터디 TIL 15일차] 치킨배달 (feat. 완전탐색)

1) 문제

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

 

2) 문제 풀이

선택된 M개의 치킨집을 기준으로 최소 도시 치킨 거리를 계산하는 방식

import java.util.*;

public class Main {
    static int N, M;
    static List<int[]> houses = new ArrayList<>();
    static List<int[]> chickens = new ArrayList<>();
    static int minCityChickenDistance = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int value = sc.nextInt();
                if (value == 1) houses.add(new int[]{i, j});
                else if (value == 2) chickens.add(new int[]{i, j});
            }
        }
        
        selectChickens(new ArrayList<>(), 0);
        System.out.println(minCityChickenDistance);
    }
    
    static void selectChickens(List<int[]> selected, int start) {
        if (selected.size() == M) {
            minCityChickenDistance = Math.min(minCityChickenDistance, computeCityChickenDistance(selected));
            return;
        }
        
        for (int i = start; i < chickens.size(); i++) {
            selected.add(chickens.get(i));
            selectChickens(selected, i + 1);
            selected.remove(selected.size() - 1);
        }
    }
    
    static int computeCityChickenDistance(List<int[]> selectedChickens) {
        int totalDistance = 0;
        for (int[] house : houses) {
            int minDistance = Integer.MAX_VALUE;
            for (int[] chicken : selectedChickens) {
                int distance = Math.abs(house[0] - chicken[0]) + Math.abs(house[1] - chicken[1]);
                minDistance = Math.min(minDistance, distance);
            }
            totalDistance += minDistance;
        }
        return totalDistance;
    }
}