(Java) 백준 15686 - 치킨 배달

예전에 풀었던 프로그래머스 거리두기 확인하기와 비슷하다고 느낀 문제였다.
이번 문제는 탐색보다 구현에 더 초점이 맞춰져 있던 것 같다.
요즘 코테를 보면서 느낀 코테 트렌트는 구현인 것 같다.
특정한 알고리즘을 알아야 풀 수 있는 문제도 몇 문제 있었지만 대부분이 구현 문제였다.
그래서 구현 문제를 중심으로 연습해야 할 것 같다.

문제를 읽고 이렇게 나누어 로직을 짰다.
1. 치킨 집중에서 m개를 선택해 조합 구하기
2. 구한 조합으로 각 집마다 치킨 거리 구하여 최솟값을 선택
3. 각 집에 최솟값을 더하여 도시의 치킨 거리 구하기
4. 모든 조합을 돌면서 도시의 치킨 거리의 최솟값을 반환

다만 이 로직이 맞는지 확신이 들지 않았지만 떠오르는 게 이 방법밖에 없어 코드로 구현했다.
구현하며 몇 번 막혔던 적이 있는데 처음에는 치킨집과 집을 Map에 넣었었다. Map에 KeySet을 통해서
좌표를 구하려고 했는데 Set을 하나씩 꺼내는 게 쉽지 않았다.
또, 치킨집들의 조합을 구하는 게 묘하게 어려워서 시간이 많이 걸렸다.
순열, 조합, 중복 조합은 자유롭게 쓸 수 있게 연습해야 할 것 같다.

---

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n, m, min;
    static int[] com;
    static ArrayList<int[]> chickenList;
    static ArrayList<int[]> homeList;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][n];
        chickenList = new ArrayList<>();
        homeList = new ArrayList<>();
        // 조합을 저장할 배열
        com = new int[m];
        min = Integer.MAX_VALUE;

        // 입력값 배열 삽입 및 list에 치킨집과 집 삽입
        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] == 2) {
                    chickenList.add(new int[]{i, j});
                } else if (arr[i][j] == 1) {
                    homeList.add(new int[]{i, j});
                }
            }
        }
        combination(0, 0);
        System.out.println(min);
    }

    // 조합을 구하는 메서드
    static void combination(int idx, int depth) {
        // 조합이 하나 만들어지면 도시 치킨거리 구하기
        if (depth == m) {
            min = Math.min(minLength(), min);
            return;
        }
        for (int i = idx; i < chickenList.size(); i++) {
            com[depth] = i;
            combination(i + 1, depth + 1);
        }
    }

    // 조합에서 치킨거리 구하기
    static int minLength() {
        int sum = 0;
        for (int[] homeTemp : homeList) {
            int chickenLength = Integer.MAX_VALUE;
            int hx = homeTemp[0];
            int hy = homeTemp[1];

            for (int i = 0; i < com.length; i++) {
                int[] chickenTemp = chickenList.get(com[i]);
                int cx = chickenTemp[0];
                int cy = chickenTemp[1];

                // 각 집의 치킨거리
                chickenLength = Math.min(Math.abs(hx - cx) + Math.abs(hy - cy), chickenLength);
            }
            // 현재 조합에서 도시 치킨거리
            sum += chickenLength;
        }
        return sum;
    }
}