[BOJ] 15686번 치킨 배달

개요

도시에 있는 치킨집중 몇개를 폐업시켜 최대 이익을 낼 수 있는지 탐색하는 문제

문제링크

코드

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Baekjoon15686 {
    static int N, M;
    static ArrayList<int[]> house;
    static ArrayList<int[]> chicken;
    static int min;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        house = new ArrayList<>();
        chicken = new ArrayList<>();

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

        min = Integer.MAX_VALUE;
        combi(0, 0, new int[M]);

        bw.write(min+"\n");
        bw.close();

    }

    public static void combi(int start, int cnt, int[] combiChicken) {
        if (cnt == M) {
            distance(combiChicken);
            return;
        }
        for (int i = start; i < chicken.size(); i++) {
            combiChicken[cnt] = i;
            combi(i+1, cnt+1, combiChicken);
        }
    }

    public static void distance(int[] combiChicken) {
        int result = 0;
        for (int i = 0; i < house.size(); i++) {
            int[] h = house.get(i);
            int distance = Integer.MAX_VALUE;
            for (int j = 0; j < combiChicken.length; j++) {
                int[] c = chicken.get(combiChicken[j]);
                distance = Math.min((int)Math.abs(h[0] - c[0]) + (int)Math.abs(h[1] - c[1]), distance);
            }
            result += distance;
        }
        min = Math.min(result, min);
    }

}

해결 과정

선택될 수 있는 치킨집은 최대 13개(M<=13)이고 집의 개수는 2N개(N <= 50)를 넘지 않으니깐 모든 경우의 수를 확인해 최대이익을 계산해도 문제없겠다고 생각해 완전 탐색을 사용해 해결하였다.

사용된 알고리즘은 다음과 같다.

1. 현재 지도에 있는 치킨집의 좌표를 ArrayList에 저장
2. 치킨집을 M개 뽑은 뒤에 치킨거리를 계산
3. 현재 저장된 최소거리보다 작으면 갱신
4. 2번 3번을 모든 경우의 수를 뽑을 떄까지 반복

결과