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

문제

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

15686번: 치킨 배달

5 2
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은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

 

풀이

Combination 을 재귀함수로 구현할 수 있어야 한다. 

 

1. 치킨집과 집의 좌표를 저장한다.

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++){
                int val = Integer.parseInt(st.nextToken());
                if(val == 1){
                    // 집의 좌표 저장
                    houses.add(new Node(i, j));
                } else if (val == 2){
                    // 치킨집 좌표 저장
                    chickens.add(new Node(i, j));
                }
            }
        }

 

2. 재귀함수를 이용하여 치킨 집 M개를 선택한다.

 select(0, 0);

    public static void select(int idx, int k){
        if(k == M){
            // M개 선택했다.
 		return;
        }
        for(int i = idx; i < chickens.size(); i++){
            Node chicken = chickens.get(i);
            if(selected.contains(chicken)) continue;
            selected.add(chicken);
            select(i+1, k+1);
            selected.remove(chicken);
        }
    }

3. M개가 선택되었다면, 집의 좌표를 순회하면서 선택된 치킨집과 거리를 계산한다.

이 중 가장 최소 거리를 totalDistance(도시의 치킨 거리)에 더해나간다. 

      if(k == M){
            // M개 선택했다.
            int totalDistance = 0;
            for(Node h: houses){
                int min = Integer.MAX_VALUE;
                for(Node s : selected){
                    min = Math.min(min, (Math.abs(h.x - s.x) + Math.abs(h.y - s.y)));
                }
                totalDistance += min;
            }
            answer = Math.min(answer, totalDistance);
            return;
        }

4. M개가 선택될 때마다 totalDistance(도시의 치킨 거리)가 계산되며, 그 중 최소 값이 답이 된다.

            answer = Math.min(answer, totalDistance);
            return;

 

소스코드

Java

package bruteforce;

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

public class BOJ15686 {
    public static class Node {
        int x;
        int y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static int N, M, answer;
    public static ArrayList<Node> chickens, houses, selected;
    public static boolean[] visited;
    public static void main(String[] args) 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());
        chickens = new ArrayList<Node>();
        houses = new ArrayList<Node>();
        selected = new ArrayList<Node>();

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++){
                int val = Integer.parseInt(st.nextToken());
                if(val == 1){
                    // 집의 좌표 저장
                    houses.add(new Node(i, j));
                } else if (val == 2){
                    // 치킨집 좌표 저장
                    chickens.add(new Node(i, j));
                }
            }
        }

        answer = Integer.MAX_VALUE;
        // 치킨 집 M개 선택했을 때, 집과 치킨집 최소거리의 합 구해서
        // 그 중 제일 작은 값
        select(0, 0);

        System.out.println(answer);
    }


    public static void select(int idx, int k){
        if(k == M){
            // M개 선택했다.
            int totalDistance = 0;
            for(Node h: houses){
                int min = Integer.MAX_VALUE;
                for(Node s : selected){
                    min = Math.min(min, (Math.abs(h.x - s.x) + Math.abs(h.y - s.y)));
                }
                totalDistance += min;
            }
            answer = Math.min(answer, totalDistance);
            return;
        }
        for(int i = idx; i < chickens.size(); i++){
            Node chicken = chickens.get(i);
            if(selected.contains(chicken)) continue;
            selected.add(chicken);
            select(i+1, k+1);
            selected.remove(chicken);
        }
    }
}

 

Python

 

 

import itertools

n, m = map(int, input().split())
arr = [[0]*(n+1) for _ in range(n+1)]

chickens = []
homes = []
answer = 1e9

for i in range(1, n+1):
    data = list(map(int, input().split()))
    for j in range(1, n+1):
        arr[i][j] = data[j-1]
        if arr[i][j] == 2:
            chickens.append((i, j))
        if arr[i][j] == 1:
            homes.append((i, j))


select_list = list(itertools.combinations(chickens, m))

for selected in select_list:
    total_dist = 0
    for home in homes:
        dist = 1e9
        hx, hy = home
        for sel in selected:
            sx, sy = sel
            dist = min(dist, abs(hx - sx) + abs(hy - sy))
        total_dist += dist
    answer = min(answer, total_dist)
print(answer)