[Algorithm/Java] 백준 15686번 - 치킨 배달

---

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

---

🔍 문제 풀이

문제 도식화

선택된 치킨집을 배열로 관리

• 배열 choiceChicken[depth]를 사용하면, 특정 깊이의 선택이 덮어쓰여지므로 따로 “선택 해제”를 할 필요가 없음.
• 즉, 배열 덮어쓰기로 백트래킹이 자동으로 구현됨.
• 리스트 사용시 choiceChicken.remove(choiceChicken.size() - 1); 와 같이 명시적으로 지워야 함

💻 코드

각 집마다 최적의 치킨집을 찾아야 하므로(1:n), 집을 고정하고 (바깥) 치킨집들을 순회 (안쪽)해야함

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[][] arr;

    static int ans = Integer.MAX_VALUE;

    static List<Pos> home = new ArrayList<>();
    static List<Pos> chicken = new ArrayList<>();
    static Pos[] choiceChicken;

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

        // input
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][n];
        choiceChicken = new Pos[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 Pos(i, j));
                else if(arr[i][j] == 2) chicken.add(new Pos(i, j));
            }
        }

        // solve
        dfs(0, 0);

        // print
        System.out.println(ans);
    }

    static void dfs(int depth, int start) {
        if(depth == m) {
            int totalDist = 0;

            for(Pos h : home) {
                int minDist = Integer.MAX_VALUE; // 각 집과 가장 가까운 치킨집 거리

                for(Pos c : choiceChicken) {
                    int dist = Math.abs(h.x - c.x) + Math.abs(h.y - c.y);
                    minDist = Math.min(minDist, dist);
                }
                totalDist += minDist;
            }

            ans = Math.min(ans, totalDist);
            return;
        }

        // 조합
        for(int i = start; i<chicken.size(); i++) {
            choiceChicken[depth] = chicken.get(i); // 선택
            dfs(depth + 1, i + 1); // 다음 치킨집 선택
        }
    }

    static class Pos {
        int x, y;

        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}