문제 링크

접근 방식

• 집이랑 치킨집을 따로 ArrayList로 관리
• dfs로 깊이가 M이면 치킨거리 계산해서 최소치킨거리 계산하게!
• 한번 selected에 들어가서 조합 처리됐으면 백트래킹으로 복구시켜놓기

👉 치킨집 M개 조합을 전부 탐색해서 최솟값을 구하는 문제

코드 설명

조합 생성 (combi)

static void combi(List<int[]> selected, int start, int depth)

• 치킨집 중 M개를 선택하는 모든 조합 생성

파라미터

파라미터	의미
selected	현재 선택된 치킨집 목록
start	다음에 고를 치킨집 시작 인덱스
depth	현재 선택한 개수

조합 로직

for (int i = start; i < chickens.size(); i++) {
    selected.add(chickens.get(i));
    combi(selected, i + 1, depth + 1);
    selected.remove(selected.size() - 1);
}

• 중복 없는 조합
• i + 1부터 탐색 → 이미 선택한 치킨집 재사용 X
• DFS + 백트래킹 구조

📌 예시
치킨집 5개 중 M=3이면
→ (0,1,2), (0,1,3), (0,1,4), ...

도시 치킨 거리 계산

static int getCityChickenDistance(List<int[]> selected)

for (int[] home : homes) {
    int minDist = Integer.MAX_VALUE;
    for (int[] chicken : selected) {
        int dist = Math.abs(home[0]- chicken[0]) 
                 + Math.abs(home[1] - chicken[1]);
        minDist = Math.min(minDist, dist);
    }
    sum += minDist;
}

• 각 집마다:

  • 선택된 치킨집들과의 거리 중 최솟값 계산

• 모든 집의 최소 거리 합 → 도시 치킨 거리

정답 코드

public class BOJ_15686_치킨배달_G5 {
    static int N, M;
    static int[][] arr;
    static List<int[]> homes = new ArrayList<>();
    static List<int[]> chickens = new ArrayList<>();
    static int min = Integer.MAX_VALUE;

    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()); // 치킨 집 수
        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1)
                    homes.add(new int[]{i, j});
                if (arr[i][j] == 2)
                    chickens.add(new int[]{i, j});
            }
        }

        combi(new ArrayList<>(), 0, 0);
        System.out.println(min);
    }

    static void combi(List<int[]> selected, int start, int depth) {
        if (depth == M) {
            min = Math.min(min, getCityChickenDistance(selected));
            return;
        }

        for (int i = start; i< chickens.size(); i++) {
            selected.add(chickens.get(i));
            combi(selected, i+1, depth+1);
            selected.remove(selected.size()-1);
        }
    }

    static int getCityChickenDistance(List<int[]> selected) {
        int sum = 0;
        for (int[] home : homes) {
            int minDist = Integer.MAX_VALUE;
            for (int[] chicken : selected) {
                int dist = Math.abs(home[0]- chicken[0]) + Math.abs(home[1] - chicken[1]);
                minDist = Math.min(minDist, dist);
            }
            sum+= minDist;
        }
        return sum;
    }
}