백준 치킨 배달

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다.
집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다.
치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

내가 이 문제를 보고 생각해본 부분

BufferedReader를 사용해 입력을 효율적으로 처리하고 있다.
첫 줄에서 도시 크기 N과 선택할 치킨집 개수 M을 받아오고,
다음 N줄에 도시의 각 칸 정보를 입력받아 2차원 배열 city에 저장한다.
입력을 처리하면서, 각 칸이 집일 경우 houses 리스트에, 치킨집일 경우 chickenStores 리스트에 좌표를 저장한다.
이때 좌표는 배열 [행, 열] 형태로 저장해서 나중에 거리 계산에 바로 사용할 수 있게 한다.
chooseChickenStores 메서드는 재귀적으로 치킨집 목록에서 M개를 선택하는 “조합(combination)”을 구한다.
start는 현재 탐색 시작 인덱스, depth는 선택된 치킨집 개수를 나타낸다.
depth가 M이 되면 한 가지 조합이 완성된 상태이므로, 이 조합을 이용해 도시 치킨 거리의 총합을 계산한다.
치킨 거리 계산은, 모든 집을 순회하며 현재 선택된 치킨집들 중 가장 가까운 치킨집과의 거리를 구해 합산하는 방식이다.
거리는 행 차이와 열 차이의 절댓값 합(맨해튼 거리)으로 계산한다.
각 집마다 최소 거리를 계속 비교해 갱신하면서 도시 치킨 거리 합을 구한다.
각 조합마다 계산한 도시 치킨 거리 합 중 최소값을 minDistanceSum에 저장해둔다.
모든 조합 탐색이 완료되면 minDistanceSum을 출력한다.
마지막에 리소스 누수를 막기 위해 br.close()로 스트림을 닫는다.

코드로 구현

package baekjoon.baekjoon_33;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

// 백준 15686번 문제
public class Main1303 {
    static int N, M;
    static int[][] city;
    static List<int[]> houses = new ArrayList<>();
    static List<int[]> chickenStores = new ArrayList<>();
    static int minDistanceSum = Integer.MAX_VALUE;
    static int[] selectedIndices;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        city = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                city[i][j] = Integer.parseInt(st.nextToken());
                if (city[i][j] == 1) houses.add(new int[]{i, j});
                else if (city[i][j] == 2) chickenStores.add(new int[]{i, j});
            }
        }

        selectedIndices = new int[M];
        chooseChickenStores(0, 0);
        System.out.println(minDistanceSum);
        br.close();
    }

    // 조합으로 치킨집 M개 선택
    static void chooseChickenStores(int start, int depth) {
        if (depth == M) {
            int totalDistance = 0;
            // 모든 집에 대해 선택된 치킨집 중 최소 거리 계산
            for (int[] house : houses) {
                int houseMinDist = Integer.MAX_VALUE;
                for (int idx : selectedIndices) {
                    int[] chicken = chickenStores.get(idx);
                    int dist = Math.abs(house[0] - chicken[0]) + Math.abs(house[1] - chicken[1]);
                    if (dist < houseMinDist) houseMinDist = dist;
                }
                totalDistance += houseMinDist;
            }
            if (totalDistance < minDistanceSum) minDistanceSum = totalDistance;
            return;
        }

        for (int i = start; i < chickenStores.size(); i++) {
            selectedIndices[depth] = i;
            chooseChickenStores(i + 1, depth + 1);
        }
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.