[B15686][치킨 배달][java]

 

 

풀이

처음에는 시간초과났다.
나는 치킨집 전체에서 하나씩 제거해가며 m 개수에 맞춰서 경우의 수 계산
수정된 코드는 0개부터 시작해서 m개만큼 골라서 경우의 수 계산

ex. 13개 중에 2개 뽑기
→ 11개를 제거해야 하니 비효율적
→ 2개씩 골라서 경우의 수 계산해나가는 게 정답.

 

코드

 

public class B15686 {
    public static class Point {
        int x, y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static int n, m, distance;
    static int[][] city;
    static boolean[] isVisit;
    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];

        List<Point> chicken = new ArrayList<>();
        List<Point> house = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String[] tmp = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                city[i][j] = Integer.parseInt(tmp[j]);
                if(city[i][j] == 2) chicken.add(new Point(i, j));
                if(city[i][j] == 1) house.add(new Point(i, j));
            }
        }

        distance = Integer.MAX_VALUE;
        isVisit = new boolean[chicken.size()];
        dfs(0, 0, chicken, house);
        System.out.println(distance);
    }

    public static void dfs(int start, int cnt, List<Point> chicken, List<Point> house) {
        if(cnt == m){
            distance = Math.min(distance, getChickenStreet(chicken, house));
            return;
        }

        for (int i = start; i < chicken.size(); i++) {
            isVisit[i] = true;
            dfs(i + 1, cnt + 1, chicken, house);
            isVisit[i] = false;
        }
    }

    public static int getChickenStreet(List<Point> chicken, List<Point> house) {
        int dis = 0;

        // 이 도시의 치킨 거리 구하기
        for(Point h : house){
            int minNum = Integer.MAX_VALUE;
            for (int i = 0; i < chicken.size(); i++) {
                if(isVisit[i]) minNum = Math.min(Math.abs(h.x - chicken.get(i).x) + Math.abs(h.y - chicken.get(i).y), minNum);
            }
            dis += minNum;
        }
        return dis;
    }
}