[BOJ 15686] 치킨 배달 (Java, DFS)

 

---

문제 링크 

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

15686번: 치킨 배달

---

풀이 

- 주어진 치킨 집 중에 최대 M개 선택(조합)하여, 도시의 치킨 거리의 최솟값을 출력함

- 집의 개수는 N = 50 일때 최대 100개까지 가능

- 치킨집 개수는 최대 M = 13  

 

1) 초기화

치킨집(2)과 집(1)의 좌표를 담은 리스트 구함

 

2) 치킨집 조합 구하기 

조합 (Combination, nCr) : 서로 다른 n개 중에 r개를 중복없이 뽑음, 이때 순서 구분 없음 (중요*)

1 2 3 중에 2개를 뽑는 조합을 구할 경우 

1 2      -- 순서 구분 없기 때문에 (2,1) = (1,2) 동일한 조합이라고 봄
1 3
2 3

3C2 = 3P2 / 2! = 3 * 2 / 2! = 3 

이때 순열로 구하게 될 경우 중복 연산 처리가 되서 '시간 초과' 발생함

- 순열로 구할 경우 치킨집은 nPr = 13P6 = 1,235,520 경우의 수 발생 

- 조합으로 구할 경우 치킨집은 nCr = 13C6 = 1716 경우의 수 발생

 

3) 치킨집 조합과 집과의 '치킨 거리' 계산 후 합산하여 '도시의 치킨 거리'의 최소값 구하기

- '치킨 거리'는 집과 가장 가까운 치킨집 사이의 거리이다.
- '도시의 치킨 거리'는 모든 집의 '치킨 거리'의 합이다

 

---

제출 코드

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

public class Main {
    
    static int N, M, RESULT;

    static List<Node> house = new ArrayList<>();

    static List<Node> chickenStore = new ArrayList<>();

    static int[] selected;

    static class Node {
        int x;
        int y;

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

    static void input() 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());

        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++) {
                int value = Integer.parseInt(st.nextToken());

                if(value == 1) house.add(new Node(i, j));
                else if(value == 2) chickenStore.add(new Node(i, j));
            }
        }

        selected = new int[M]; // M개 만큼 선택
        RESULT = Integer.MAX_VALUE;

        br.close();
    }

    static void dfs(int cnt, int start) {
        if(cnt == M) {
            int totalDistance = 0;
            for(Node h : house) {
                int distance = Integer.MAX_VALUE;
                for(int idx : selected) {
                    Node c = chickenStore.get(idx);
                    distance = Math.min(distance, Math.abs(h.x - c.x) + Math.abs(h.y - c.y));
                }
                totalDistance += distance;
            }

            RESULT = Math.min(RESULT, totalDistance);
            return;
        }

        for(int i = start; i < chickenStore.size(); i++) {
            selected[cnt] = i;
            dfs(cnt + 1, i + 1);
            selected[cnt] = 0;
        }
    }

    static void pro() {
        dfs(0, 0);
        System.out.println(RESULT);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}