[백준 - G5] 15686. 치킨 배달

문제

M개 만큼의 치킨집을 선택해, 각 치킨 집과 집의 최소 거리를 모두 더해 도시의 치킨 거리가 가장 작게 될지 구하는 문제

예시)

• 집 위치: (0,3), (1,0), (1,2), (3,3), (3,4), (4,3)
• 치킨 집 위치: (0,1), (3,0), (4,0), (4,1), (4,4)

0 2 0 1 0 
1 0 1 0 0 
0 0 0 0 0 
2 0 0 1 1 
2 2 0 1 2

• 정답을 만드는 조합은 (0,1) 과 (4,4)

🏠 H1 (0,3)

• C1(0,1): |0-0| + |3-1| = 2
• C5(4,4): |0-4| + |3-4| = 5
  → 최소 = 2

🏠 H2 (1,0)

• C1: |1-0| + |0-1| = 2
• C5: |1-4| + |0-4| = 7
  → 최소 = 2

🏠 H3 (1,2)

• C1: |1-0| + |2-1| = 2
• C5: |1-4| + |2-4| = 5
  → 최소 = 2

🏠 H4 (3,3)

• C1: |3-0| + |3-1| = 5
• C5: |3-4| + |3-4| = 2
  → 최소 = 2

🏠 H5 (3,4)

• C1: |3-0| + |4-1| = 6
• C5: |3-4| + |4-4| = 1
  → 최소 = 1

🏠 H6 (4,3)

• C1: |4-0| + |3-1| = 6
• C5: |4-4| + |3-4| = 1
  → 최소 = 1

따라서, 정답은 2 + 2 + 2 + 2 + 1 + 1 = 10 이 된다.

 

---

1. 치킨집 좌표중 M개의 치킨집 선택하기

• 치킨 집의 좌표를 List에 넣고 그 중 조합을 활용해 M개의 좌표를 선택한다.
• M개가 선택되면, 집 당 가장 최소 거리의 치킨 값을 모두 더한다.
• 모든 최소 거리의 합 중 가장 작은 값이 정답!

static void combi(int cnt, int start, List<int[]> chickens) {

        if (cnt == M) {
            int sum = 0;
            // 집별 모든 치킨 거리(한 집에서 모든 치킨집의 최소)
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == 1) { // 집
                        sum += calcDir(chickens, i, j);
                    }
                }
            }
            V = Math.min(sum, V);
            return;
        }

        for (int i = start; i < chickens.size(); i++) {
            if (!chooseChicken[i]) {
                chooseChicken[i] = true;
                combi(cnt + 1, i + 1, chickens);
                chooseChicken[i] = false;
            }
        }

}

 

2. 집 당 모든 치킨 거리의 최소값 구하기

static int calcDir(List<int[]> chickens, int x, int y) {

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < chooseChicken.length; i++) {
            if (chooseChicken[i]) {
                int nx = Math.abs(chickens.get(i)[0] - x);
                int ny = Math.abs(chickens.get(i)[1] - y);

                min = Math.min(min, nx + ny);
            }

        }

        return min;
    }

---

틀렸던 부분

1. 조합을 한 번만 구하면 되는데 M번 호출하여 불필요한 탐색이 발생했다

치킨집 중에서 M개를 고르는 조합은 한 번의 DFS로 모두 생성 가능하다.
그런데 아래 코드에서는 시작 인덱스를 달리하여 combi를 M번 호출하고 있어,
같은 조합 공간을 여러 번 중복 탐색하게 된다.

for (int i = 0; i < M; i++) { 
    combi(0, i, chickens); 
}

→ combi(0, 0, chickens) 한 번만 호출하면 충분

2. 다음 재귀 호출에서 시작 인덱스를 start + 1로 넘긴 것이 조합 규칙을 깨뜨렸다

combi를 진행할 때, 다음 인덱스를 i + 1로 해야하는데 계속 start + 1로 실행하였다.

• 이렇게 될 경우, 방금 선택한 인덱스와 다음 탐색 범위가 연결되지 않고, 이미 선택한 인덱스를 다시 선택해 중복이 포함된 탐색이 될 수 있다.

for (int i = start; i < chickens.size(); i++) { 
    if (!chooseChicken[i]) { 
        chooseChicken[i] = true; 
        combi(cnt + 1, start + 1, chickens);  // ❌ 잘못된 부분
        chooseChicken[i] = false; 
    } 
}

---

전체 코드

public class Main {

    static int N, M, V;
    static int[][] map;
    static boolean[] chooseChicken;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");

        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        V = Integer.MAX_VALUE;

        map = new int[N][N];
        List<int[]> chickens = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            split = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(split[j]);
                if (map[i][j] == 2) {
                    chickens.add(new int[] { i, j });
                }
            }
        }

        chooseChicken = new boolean[chickens.size()];
        combi(0, 0, chickens);

        System.out.println(V);

    }

    static void combi(int cnt, int start, List<int[]> chickens) {

        if (cnt == M) {
            int sum = 0;
            // 집별 모든 치킨 거리(한 집에서 모든 치킨집의 최소)
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == 1) { // 집
                        sum += calcDir(chickens, i, j);
                    }
                }
            }
            V = Math.min(sum, V);
            return;
        }

        for (int i = start; i < chickens.size(); i++) {
            if (!chooseChicken[i]) {
                chooseChicken[i] = true;
                combi(cnt + 1, i + 1, chickens);
                chooseChicken[i] = false;
            }
        }

    }

    static int calcDir(List<int[]> chickens, int x, int y) {

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < chooseChicken.length; i++) {
            if (chooseChicken[i]) {
                int nx = Math.abs(chickens.get(i)[0] - x);
                int ny = Math.abs(chickens.get(i)[1] - y);

                min = Math.min(min, nx + ny);
            }

        }

        return min;
    }
}

문제 링크

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