[알고리즘 / 백준] 15686 - 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

문제는 위와 같으며, 남겨질 치킨집을 조합으로 구해서 남겨진 치킨집들 중 각 집에서 최소거리에 있는 치킨집을 찾아 그 거리를 더해 도시의 치킨 거리를 구합니다. 조합을 모두 확인하면서 도시의 치킨 거리의 최소값을 갱신해서 최종적으로 저장된 도시의 치킨거리를 출력합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
from itertools import combinations


# 남겨진 치킨집에 대해 도시의 최소 치킨거리 구하기
def find_min_dist(chicken):
    min_dist = 0
    for hx, hy in home:  # 각 집의 위치 구하기
        min_dist_per_home = 101
        for cx, cy in chicken:  # 남겨진 치킨집을 하나씩 찾아
            dist = abs(hx - cx) + abs(hy - cy)  # 집과 치킨집 사이의 거리를 구하고
            min_dist_per_home = min(min_dist_per_home, dist)  # 가장 가까운 치킨집의 거리를 저장
        min_dist += min_dist_per_home  # 도시의 치킨 거리에 추가

    return min_dist  # 도시의 치킨 거리 반환


n, m = map(int, stdin.readline().split())
home = []  # 집의 위치 저장 [[x, y], [..], ..]
chickens = []  # 치킨집의 위치 저장 [[x, y], [..], ..]
for i in range(n):
    tmp = list(map(int, stdin.readline().split()))
    for j in range(n):
        if tmp[j] == 1:
            home.append([i, j])
        elif tmp[j] == 2:
            chickens.append([i, j])

result = -1  # 최소 도시 치킨 거리

# 전체 치킨집 중에서 m개를 뽑아
# 남겨진 치킨집으로 생각하고 find_min_dist 에 전달
for combi in combinations(chickens, m):
    # 기존 도시의 치킨 거리와 비교하여 더 작은 값 저장
    result = find_min_dist(combi) if result == -1 else min(result, find_min_dist(combi))

print(result)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static ArrayList<int[]> home = new ArrayList<>();  // 집의 위치 저장
    private static ArrayList<int[]> chickens = new ArrayList<>();  // 치킨집의 위치 저장

    private static ArrayList<ArrayList<int[]>> combi = new ArrayList<>();  // 조합을 통해 m개씩 묶인 치킨집의 위치를 저장

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 집, 치킨집의 위치 찾아서 저장
        for (int i = 0; i < n; i++) {
            int[] city = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < n; j++) {
                if (city[j] == 1) {
                    home.add(new int[]{i, j});
                } else if (city[j] == 2) {
                    chickens.add(new int[]{i, j});
                }
            }
        }

        // 조합을 통해 m개씩 치킨집 묶기
        combinations(new boolean[chickens.size()], 0, m);

        int result = -1;
        
        // 조합에서 하나의 경우씩을 빼서
        // 도시의 최소 거리를 구하고
        // 기존 도시의 치킨거리와 비교해 더 작은 값을 저장
        for (ArrayList<int[]> c : combi) {
            if (result == -1) {
                result = findMinDist(c);
            } else {
                result = Math.min(result, findMinDist(c));
            }
        }

        System.out.println(result);
    }

    // 조합으로 m개 구하기
    private static void combinations(boolean[] visited, int start, int r) {
        if (r == 0) {
            ArrayList<int[]> tmp = new ArrayList<>();
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {  // 선택한 요소의 인덱스를 찾아
                    tmp.add(chickens.get(i));  // 해당 인덱스의 치킨집 위치를 저장
                }
            }
            combi.add(tmp);
            return;
        } else {
            for (int i = start; i < visited.length; i++) {
                visited[i] = true;  // i 번째 요소를 선택하는 경우
                combinations(visited, i + 1, r - 1);
                visited[i] = false;  // i 번째 요소를 선택하지 않는 경우
            }
        }

    }

    // 도시의 치킨 거리 구하기
    private static int findMinDist(ArrayList<int[]> chicken) {
        int minDist = 0;
        for (int[] h : home) {  // 모든 집을 하나씩 확인하면서 
            int minDistPerHome = 101;
            for (int[] c : chicken) {  // 남겨진 치킨집을 하나씩 뽑아
                int dist = Math.abs(h[0] - c[0]) + Math.abs(h[1] - c[1]);  // 집과 치킨집 사이의 거리를 구하고
                minDistPerHome = Math.min(minDistPerHome, dist);  // 최소 거리인 경우 치킨 거리로 저장
            }
            minDist += minDistPerHome;  // 도시의 치킨 거리에 추가
        }

        return minDist;
    }
}