[JAVA] 백준 15686 치킨 배달

 

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

문제분석

백트래킹 문제다. 골드 5인데도 어려움을 느끼는거 보면,,소마 합격하긴 글른거같기도..ㅠㅠ

치킨 거리를 최소로 만드는 문제다. 도시에는 여러 개의 집과 치킨집이 존재하며, 이 중에서 정확히 M개의 치킨집만을 남겨야 한다. 각 집은 선택된 치킨집들 중 가장 가까운 치킨집과의 거리를 자신의 치킨 거리로 가지게 되고, 도시의 치킨 거리는 모든 집의 치킨 거리 합으로 정의된다. 결국 문제의 핵심은 치킨집 후보들 중 M개를 선택하는 모든 경우를 탐색하면서, 각 선택 조합에 대해 도시 치킨 거리의 합을 계산하고 그 최솟값을 찾는 것이다.

 

치킨집의 개수는 최대 13개이므로, M개를 선택하는 조합의 수는 최대 13C6 수준으로 충분히 완전탐색이 가능하다. 따라서 먼저 모든 집과 치킨집 사이의 거리를 미리 계산해 2차원 배열에 저장해두고, 이후 조합을 통해 선택된 치킨집 인덱스 집합에 대해서만 각 집의 최소 거리를 빠르게 계산하는 방식이 효율적이다. 이 문제는 BFS나 DP가 아니라, “거리 사전 계산 + 조합(백트래킹)” 구조로 해결하는 전형적인 완전탐색 문제라고 볼 수 있다.

 

 

코드

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

public class Main {
    static List<int[]> home = new ArrayList<>(); // 집 위치. row, col
    static List<int[]> chick = new ArrayList<>(); // 치킨집 위치. row + col
    static int[][] allChickDist; // [homeIdx][chickIdx], 치킨 거리를 value로
    static int min = Integer.MAX_VALUE; // 최소 치킨 거리
    static int M; // 살리는 치킨집 최대 갯수
    static int[] pickedChickIdxArr;

    // start는 start까지 탐색했다. dept는 dept개 탐색했다.
    static void comb(int start, int dept) {
        // pickedChickIdxArr 배열을 다 채운 경우
        if (dept == M) {
            int result = 0;
            for (int i = 0; i < home.size(); i++) {
                int iChickDist = Integer.MAX_VALUE;
                for (int j = 0; j < dept; j++) {
                    // i번째 home과, pricked arr의 j번째를 비교하면서 i번째 home의 치킨 거리
                    iChickDist = Math.min(iChickDist, allChickDist[i][pickedChickIdxArr[j]]);
                }
                result += iChickDist;
            }
            min = Math.min(min, result);
            return;
        }

        // start 인덱스부터, chick 끝까지 중에 하나 dept 인덱스에 넣기.
        for (int i = start; i < chick.size(); i++) {
            pickedChickIdxArr[dept] = i;
            comb(i + 1, dept + 1);
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 2 ~ 50
        M = Integer.parseInt(st.nextToken()); // 1 ~ 13
        pickedChickIdxArr = new int[M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int[] locate = new int[] { i, j };
                String s = st.nextToken();
                if (s.equals("1")) {
                    home.add(locate);
                } else if (s.equals("2")) {
                    chick.add(locate);
                }
            }
        }

        allChickDist = new int[2 * N][chick.size()]; // 최대 크기가 집 위치는 2N개, 치킨집은 M

        for (int i = 0; i < home.size(); i++) {
            for (int j = 0; j < chick.size(); j++) {
                // i번째 집 위치와, j번째 치킨집 위치 거리 계산해서 allChickDist에 저장
                int[] homes = home.get(i);
                int[] chicks = chick.get(j);
                int homRow = homes[0];
                int homCol = homes[1];
                int chickRow = chicks[0];
                int chickCol = chicks[1];
                allChickDist[i][j] = Math.abs(homRow - chickRow) + Math.abs(homCol - chickCol);
            }
        }
        comb(0, 0);
        System.out.println(min);
    }

}