[백준 JAVA] 15686. 치킨 배달

문제 링크

---

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

접근 방법

---

집과 치킨집의 좌표를 각각 저장해둔 뒤, 가능한 치킨집 조합 중 m개를 선택하여 도시의 치킨 거리를 계산합니다.
모든 조합을 탐색하면서 최소 도시 치킨 거리를 찾습니다.

1. 치킨집의 인덱스를 조합으로 뽑는다.
2. 각 조합마다 도시의 치킨 거리를 계산한다.
3. 최소 값을 갱신한다.

소스 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.io.IOException;

public class Main {

    public static List<House> chicken = new ArrayList<>(), house = new ArrayList<>();
    public static int arr[];
    public static int m, rst = Integer.MAX_VALUE;

    public static class House {
        public int r;
        public int c;

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

    public static void recursive(int cnt, int i) {
        if (cnt == m) {
            int tmp, sum = 0, cal;

            for (int j = 0; j < house.size(); j++) {
                tmp = Integer.MAX_VALUE;

                for (int k = 0; k < m; k++) {
                    cal = Math.abs(chicken.get(arr[k]).r  - house.get(j).r) + Math.abs(chicken.get(arr[k]).c -house.get(j).c);
                    tmp = tmp > cal ? cal : tmp;
                }
                sum += tmp;
            }

            rst = rst > sum ? sum : rst;
            return;
        }

        for (int j = i; j < chicken.size(); j++) {
            arr[cnt] = j;
            recursive(cnt + 1, j + 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());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < n; j++) {
                int a = Integer.parseInt(st.nextToken());
                if (a == 1) {
                    house.add(new House(i, j));
                } else if (a == 2) {
                    chicken.add(new House(i, j));
                }
            }
        }

        recursive(0, 0);
        System.out.println(rst);
    }
}

코드 설명

---

House 클래스는 좌표를 저장하는 데 사용됩니다.
house, chicken 리스트는 각각 집과 치킨집의 위치를 저장합니다.
recursive() 함수는 백트래킹을 통해 치킨집의 조합을 구합니다.
각 조합마다 모든 집에 대해 가장 가까운 치킨집과의 거리를 더해 도시 치킨 거리를 계산합니다.
최소 값을 전역 변수 rst에 저장하여 최종 결과를 출력합니다.