[백준 / #15686] 치킨 배달 (Java)

문제 설명

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

15686번: 치킨 배달

 

 

---

문제풀이

- 치킨집들을 먼저 리스트에 저장한 후 치킨집 중 M개를 고른다.

- 고른 M개 치킨집에 대한 모든 집들의 거리를 계산하고 최솟값을 구한다.

- 각 집들에서 치킨집까지의 최솟값들을 더하여 총 치킨 거리를 구한다.

- 치킨집들 중 M개를 고른 조합에 대해서 모두 치킨 거리를 구하여 최솟값을 구한다.

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

class Pos {
    int r;
    int c;

    public Pos(int i, int j) {
        this.r = i;
        this.c = j;
    }
}

public class Main {
    static int N, M, idx;
    static List<Pos> 치킨;
    static List<Pos[]> 살아남은치킨집;
    static boolean isSelected[];

    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());
        int[][] 마을 = new int[N][N];
        살아남은치킨집 = new ArrayList<>();
        int result = 0;
        int ans = Integer.MAX_VALUE;
        치킨 = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                마을[i][j] = Integer.parseInt(st.nextToken());
                if (마을[i][j] == 2) {
                    치킨.add(new Pos(i, j));
                }
            }
        }
        isSelected = new boolean[치킨.size()];
        comb(0, 0);
        for (Pos[] ps : 살아남은치킨집) {
            result = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (마을[i][j] == 1) {
                        int minDist = Integer.MAX_VALUE;
                        for (Pos p : ps) {
                            int dist = Math.abs(i - p.r) + Math.abs(j - p.c);
                            minDist = Math.min(dist, minDist);
                        }
                        result += minDist;
                    }
                }
            }
            ans = Math.min(ans, result);
        }
        System.out.println(ans);
    }

    public static void comb(int count, int start) {
        if (count == M) {
            Pos[] temp = new Pos[M];
            int t = 0;
            for (int i = 0; i < 치킨.size(); i++) {
                if (isSelected[i]) {
                    temp[t++] = 치킨.get(i);
                }
            }
            살아남은치킨집.add(temp);
            return;
        }

        for (int i = start; i < 치킨.size(); i++) {
            isSelected[i] = true;
            comb(count + 1, i + 1);
            isSelected[i] = false;
        }
    }
}