boj 15686 치킨 배달

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

15686번: 치킨 배달

M개의 치킨집을 골라 도시의 치킨거리 합을 최소로 해야합니다.

인덱스를 이용하여 집의 좌표와 치킨집의 좌표를 각각 저장해놓습니다.

그 다음 모든 가능한 경우를 구해야하기 때문에 조합으로 고른 치킨집의 인덱스를 pick 배열에 저장하여

M개를 골랐으면 집과 고른 치킨집의 거리를 N^2으로 구하였습니다.

 

고른 인덱스의 다음 인덱스를 재귀로 보내야하는데 계속 실수하는 바람에 시간초과 한번 떴습니다 ㅠㅠ... 왜 매번 이런 실수를 반복하는지..

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][], house[][], chicken[][], pick[][];
    static int N, M, hsize, csize, ans = Integer.MAX_VALUE;
 
    static void func(int idx, int cnt) {
        if (cnt == M) {
            int sum = 0;
            for (int i = 0; i < hsize; i++) {
                int dis = Integer.MAX_VALUE;
                for (int j = 0; j < M; j++) {
                    int x = house[i][0] - pick[j][0];
                    int y = house[i][1] - pick[j][1];
                    dis = Math.min(dis, Math.abs(x) + Math.abs(y));
                }
                sum += dis;
            }
 
            ans = Math.min(ans, sum);
            return;
        }
 
        for (int i = idx; i < csize; i++) {
            pick[cnt][0] = chicken[i][0];
            pick[cnt][1] = chicken[i][1];
            func(i + 1, cnt + 1);
            pick[cnt][0] = 0;
            pick[cnt][1] = 0;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N][N];
        house = new int[100][2];
        chicken = new int[13][2];
        pick = new int[13][2];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 1) {
                    house[hsize][0] = i;
                    house[hsize++][1] = j;
                } else if (list[i][j] == 2) {
                    chicken[csize][0] = i;
                    chicken[csize++][1] = j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0);
        System.out.println(ans);
    }
}