BOJ 15686 치킨 배달 [Java]

BOJ 15686 치킨 배달

1. 문제 링크

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

2. 문제 해설

백트래킹을 이용하는 문제이다. 백트래킹의 대표적인 문제 n과 m 시리즈를 업그레이드한 문제라고 생각한다.
문제를 읽어보면 구현해야할 것은 크게 2가지이다.

1. 치킨 집을 m개 고르기
2. 치킨 집을 m개 고른 각 경우의 수마다 도시의 치킨 거리 구하기

이 2가지 기능을 이용해서 어떻게 전체적인 흐름이 돌아가는지 한번 설명해보겠다.
일단 치킨 집과 집의 위치를 arraylist에 담아준다. 그 후, 백트래킹을 이용하면 치킨 집을 m개 고르는 모든 경우의 수를 구할 수 있다.
여기서 m개를 고른 각 경우의 수마다 도시의 치킨 거리를 구해주고 그 중 최솟값이 정답이 된다.

3. 코드 보기

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

public class Main {
    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int n, m;
    static int[][] arr;
    static ArrayList<Point> chicken;
    static ArrayList<Point> home;
    static int[] select;
    static int ans = Integer.MAX_VALUE;

    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 = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        chicken = new ArrayList<>();
        home = new ArrayList<>();
        select = new int[m];

        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) {
                    home.add(new Point(i, j));
                } else if (arr[i][j] == 2) {
                    chicken.add(new Point(i, j));
                }
            }
        }

        selectChicken(0, 0);

        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }

    static void selectChicken(int idx, int cnt) {
        if (cnt == m) { // 치킨 집을 m개 골랐을 경우, 도시의 치킨 거리를 구함
            int cityChickenDistance = 0;

            for (int i = 0; i < home.size(); i++) {
                int chickenDistance = Integer.MAX_VALUE;
                Point curHome = home.get(i);

                for (int j = 0; j < m; j++) {
                    Point curChicken = chicken.get(select[j]);
                    int tmpChickenDistance = getChickenDistance(curHome, curChicken);

                    if (chickenDistance > tmpChickenDistance) {
                        chickenDistance = tmpChickenDistance;
                    }
                }

                cityChickenDistance += chickenDistance;
            }

            if (ans > cityChickenDistance) {
                ans = cityChickenDistance;
            }

            return;
        }

        for (int i = idx; i < chicken.size(); i++) { // 치킨 집을 고르는 순서는 상관 없으므로 i = idx 부터 시작
            select[cnt] = i;
            selectChicken(i + 1, cnt + 1);
        }
    }

    static int getChickenDistance(Point home, Point chicken) {
        int dis = Math.abs(home.r - chicken.r) + Math.abs(home.c - chicken.c);

        return dis;
    }
}