문제 풀이 - 치킨 배달(JAVA)

치킨 배달

문제의 분할

우리가 해결해야 할 문제는 '치킨집의 개수가 $M$개까지 줄어들었을 때 도시의 치킨 거리가 가장 작은 경우의 도시의 치킨 거리를 구하라'입니다. 최적화 문제입니다. 만들 수 있는 치킨집의 모든 조합을 만들어 보고 최솟값을 구하면 됩니다. 문제를 '현재 도시의 상태에서 $M$개까지 치킨집의 개수를 줄였을 때 도시의 치킨 거리의 최솟값을 구하라'로 바꿀 수 있습니다. int getMinChickenDistance(int chickenHouseCount) 함수를 만들고 함수를 호출하면 치킨집을 하나 없애고 재귀 호출하는 식의 구현을 하면 됩니다. 단, 이 함수에서 치킨집을 하나 없앨 때 그냥 없애면 중복되는 경우까지 계산하게 됩니다. 따라서 치킨집을 없앨 순서를 강제해야 합니다. 치킨집을 없앨 때는 없앤 치킨집의 위치를 인자로 넣고 그 위치보다 뒤에 있는 치킨집만 없애면 됩니다. int getMinChickenDistance(int chickenHouseCount, int row, int column) 이렇게 만들면 됩니다.

기저 사례의 선택

만약 현재 치킨집의 개수가 입력된 인자와 같다면 도시의 치킨 거리를 반환합니다.

시간 복잡도 분석

조합의 가장 많은 경우의 수는 $\binom{13}{6}$이므로 충분히 시간 안에 계산할 수 있습니다.

구현

import java.util.*;

public class Main {

    // 도시의 크기
    public static int N;
    // 치킨집의 최대 개수
    public static int M;
    // 도시 정보
    public static int[][] city;
    // 답
    public static int result;

    // 입력값을 받는 함수입니다.
    public static void input() {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        city = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                city[i][j] = scanner.nextInt();
            }
        }
        scanner.close();
    }

    // 문제를 해결하는 함수입니다.
    public static void solve() {
        result = getMinChickenDistance(M, 0, 0);
    }

    // 도시의 치킨집을 M개까지 줄였을 때 도시의 치킨 거리의 최솟값을 반환하는 함수입니다.
    public static int getMinChickenDistance(int chickenHouseCount, int row, int column) {
        // 기저 사례 1: 만약 치킨집의 개수가 원하는 만큼 줄여졌다면 도시의 치킨 거리를 반환합니다.
        if (countChickenHouse() == chickenHouseCount) {
            return getCityChickenDistance();
        }
        // 기저 사례 2: 만약 치킨집을 지울 수 있는 위치가 도시의 범위를 벗어났다면 매우 큰 값을 반환합니다.
        if (!inRange(row, column)) return Integer.MAX_VALUE;

        int result = Integer.MAX_VALUE;
        // 인자로 받은 위치와 같거나 더 뒤에 있는 치킨집만 없애줍니다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (city[i][j] == 2 && i >= row) {
                    if (i == row && j < column) {
                        continue;
                    }
                    city[i][j] = 0;
                    result = Math.min(result, getMinChickenDistance(chickenHouseCount, i, j));
                    city[i][j] = 2;
                }
            }
        }
        return result;
    }

    // 도시의 치킨집 개수를 반환하는 함수입니다,
    public static int countChickenHouse() {
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (city[i][j] == 2) count++;
            }
        }
        return count;
    }

    // 현재 도시의 치킨 거리를 반환하는 함수입니다.
    public static int getCityChickenDistance() {
        int sum = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (city[i][j] == 1) {
                    sum += getChickenDistance(i, j);
                }
            }
        }
        return sum;
    }

    // 현재 집의 치킨 거리를 반환하는 함수입니다.
    public static int getChickenDistance(int row, int column) {
        int distance = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (city[i][j] == 2) {
                    distance = Math.min(distance, getDistance(row, column, i, j));
                }
            }
        }
        return distance;
    }

    // 두 위치 간의 거리를 반환하는 함수입니다.
    public static int getDistance(int r1, int c1, int r2, int c2) {
        return Math.abs(r2 - r1) + Math.abs(c2 - c1);
    }

    // 인자로 받은 위치가 도시의 범위인지 확인하는 함수입니다.
    public static boolean inRange(int row, int column) {
        return 0 <= row && row < N && 0 <= column && column < N;
    }

    // 답을 출력하는 함수입니다.
    public static void output() {
        System.out.println(result);
    }
    
    public static void main(String[] args) {
        input();
        solve();
        output();
    }
}

회고

처음엔 문제를 '현재 도시의 상태에서 $M$개까지 치킨집의 개수를 줄였을 때 도시의 치킨 거리의 최솟값을 구하라'로 만들고 int getMinChickenDistance(int chickenHouseCount) 함수를 만들고 함수를 호출하면 치킨집을 하나 없애고 재귀 호출하는 식의 구현을 하려 했으나 최악의 경우의 수를 계산해보니 $13!$이 나와서 할 수 없었습니다. 그래서 중복을 제거하는 식으로 구현했습니다.
chickenHoustCount는 줄이면 안되지만 줄여서 시간을 많이 잡아먹었습니다.