[BOJ/Java] 15686. 치킨 배달

[BOJ/Java] 15686. 치킨 배달

15686번: 치킨 배달

---

문제 해석

이 문제는 도시의 크기 N×N과 치킨집들 중 최대 M개를 선택하여, 도시의 치킨 거리를 최소화하는 문제이다. 여기서 치킨 거리란, 각 집에서 가장 가까운 치킨집까지의 거리의 합을 의미한다.

풀이 과정

풀이는 조합과 브루트 포스를 이용한 접근 방식을 채택하였다. 모든 치킨집의 조합을 고려하여, 각 조합마다 모든 집의 치킨 거리를 계산하고 이를 최소화한다.

• sol 함수는 재귀적으로 치킨집의 조합을 생성하고, 각 조합에 대해 도시의 치킨 거리를 계산한다.
• 선택된 치킨집에 대해 모든 집의 최소 치킨 거리를 구하고, 이들의 합을 최소화하는 방식으로 문제를 해결한다.
• 최소 거리는 ans 변수에 저장되며, 각 재귀 호출마다 갱신된다.

코드

package edu.ssafy.im.BOJ.Gold.G5.No15686;

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

public class Main {
    private int[] sel; // 치킨집 선택 배열
    private int m; // 최대 선택 가능한 치킨집 수
    private int ans = Integer.MAX_VALUE; // 최소 치킨 거리 저장 변수
    List<Point> startList, targetList; // 집과 치킨집 리스트

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        sel = new int[m]; // 선택 배열 초기화
        startList = new ArrayList<>();
        targetList = new ArrayList<>();
        for (int x = 0; x < n; x++) {
            st = new StringTokenizer(br.readLine());
            for (int y = 0; y < n; y++) {
                int location = Integer.parseInt(st.nextToken());
                if (location == 1) {
                    startList.add(new Point(x, y)); // 집 위치 추가
                } else if (location == 2) {
                    targetList.add(new Point(x, y)); // 치킨집 위치 추가
                }
            }
        }
        sol(0, 0); // 솔루션 함수 호출

        sb.append(ans);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol(int i, int k) {
        // 모든 선택이 완료된 경우
        if (k == sel.length) {
            int distanceSum = 0;
            for (int s = 0; s < startList.size(); s++) {
                int sx = startList.get(s).x;
                int sy = startList.get(s).y;

                int shortestDistance = Integer.MAX_VALUE;
                for (int targetIndex : sel) {
                    int tx = targetList.get(targetIndex).x;
                    int ty = targetList.get(targetIndex).y;

                    int distance = Math.abs(sx - tx) + Math.abs(sy - ty); // 맨해튼 거리 계산
                    shortestDistance = Math.min(shortestDistance, distance); // 최소 거리 갱신
                }

                distanceSum += shortestDistance; // 총 거리 합산
            }
            ans = Math.min(ans, distanceSum); // 최소 치킨 거리 갱신
            return;
        }
        if (i == targetList.size()) {
            return;
        }

        // 치킨집 선택
        sel[k] = i;
        sol(i + 1, k + 1); // 선택된 치킨집 포함하여 재귀 호출
        sol(i + 1, k); // 현재 치킨집을 제외하고 재귀 호출
    }

    class Point {
        int x;
        int y;

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

시간 복잡도 분석

이 문제의 시간 복잡도는 O(C(m,k)×m×h)이다, 여기서 C(m,k)는 치킨집의 조합 수, m은 최대 선택 가능한 치킨집 수, h는 집의 수를 나타낸다. 모든 조합에 대해 모든 집의 치킨 거리를 계산하기 때문에 계산이 많아질 수 있다.

느낀점

이 문제를 통해 조합과 브루트 포스 방식으로 복잡한 최적화 문제를 해결하는 방법을 배울 수 있었다. 또한, 효율적인 조합 탐색을 위한 가지치기 기법의 중요성을 다시 한번 깨달았다. 이러한 문제 해결 경험은 앞으로 더 어려운 최적화 문제에 대한 접근 방식을 개선하는 데 도움이 될 것이다.