[백준] 15686번 : 치킨 배달

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

 

 

문제

 

 

---

코드

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

public class bj_15686 {

    private static int M;
    private static final ArrayList<Node> chickens = new ArrayList<>();
    private static final ArrayList<Node> homes = new ArrayList<>();
    private static final ArrayList<Node> selected = new ArrayList<>();
    private static boolean[] visited;
    private static int result = 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());
        int N = Integer.parseInt(st.nextToken());   // 도시 크기
        M = Integer.parseInt(st.nextToken());   // 치킨 집 개수

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int info = Integer.parseInt(st.nextToken());
                if (info == 1) {
                    homes.add(new Node(i, j));
                } else if (info == 2) {
                    chickens.add(new Node(i, j));
                }
            }
        }
        visited = new boolean[chickens.size()];

        dfs(0, 0);

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int count, int start) {
        if (count == M) {
            int sum = 0;
            for (Node home : homes) {
                int min = Integer.MAX_VALUE;
                for (Node chicken : selected) {
                    int distance = Math.abs(home.x - chicken.x) + Math.abs(home.y - chicken.y);
                    min = Math.min(min, distance);
                }
                sum += min;
            }
            result = Math.min(result, sum);
            return;
        }

        for (int i = start; i < chickens.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                selected.add(chickens.get(i));
                dfs(count + 1, i + 1);
                selected.remove(chickens.get(i));
                visited[i] = false;
            }
        }


    }


    private static class Node {
        int x;
        int y;

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

 

---

풀이

변수

• `M`: 선택할 치킨집 수
• `chickens`: 치킨집 좌표 리스트
• `homes`: 집 좌표 리스트
• `selected`: 선택된 치킨집 리스트
• `visited`: 치킨집 방문 여부 표시하는 배열

 

for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < N; j++) {
        int info = Integer.parseInt(st.nextToken());
        if (info == 1) homes.add(new Node(i, j));
        else if (info == 2) chickens.add(new Node(i, j));
    }
}

• NxN을 탐색하면서 집은 `homes` 리스트에, 치킨집은 `chickens` 리스트에 저장한다.

 

private static void dfs(int count, int start) {
    if (count == M) {
        int sum = 0;
        for (Node home : homes) {
            int minDist = Integer.MAX_VALUE;
            for (Node chicken : selected) {
                int dist = Math.abs(home.x - chicken.x) + Math.abs(home.y - chicken.y);
                minDist = Math.min(minDist, dist);
            }
            sum += minDist;
        }
        result = Math.min(result, sum);
        return;
    }

    for (int i = start; i < chickens.size(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            selected.add(chickens.get(i));
            dfs(count + 1, i + 1);
            selected.remove(chickens.get(i));
            visited[i] = false;
        }
    }
}

• M개의 치킨집 선택 시: 각 집의 치킨 거리 합을 계산해 최솟값 갱신
• M개 선택 전: 백트래킹으로 선택하지 않은 치킨집 선택

 

이 문제가 이해가 잘 안되면 15649번을 풀어보는 걸 추천한다. 백트래킹을 모른 채로 이 문제를 처음 접했을 때는 감이 안 왔는데 저 문제를 풀고 나니 대충 흐름이 이해가 됐다.