채우다

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

• 알고리즘[풀이방법]

문제의 조건에서 M개의 치킨 집만 남기기 때문에, cnt에 치킨집의 개수를 넣고, cnt가 m이 될 때 거리를 계산하여 최단 거리를 갱신하였다. chicken과 house리스트를 만들고, for문을 돌려 pick을 확인하여 포함되어 있으면 최단 거리 계산! solve메서드 안에서 최소거리를 계속 확인하였다. 

전형적인 백트래킹 문제. 

package algorithm;

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

public class Chicken {
	static int n, m, ans, map[][];
	static ArrayList<int[]> house, chicken;
	static boolean pick[];

	static void solve(int start, int cnt) {
    if (cnt == m) {
        int res = 0;
        // 거리구하기
        for (int j = 0; j < house.size(); j++) {
            int tmp = Integer.MAX_VALUE;
            for (int i = 0; i < chicken.size(); i++) {
                if (pick[i]) {
                    int distance = Math.abs(chicken.get(i)[0] - house.get(j)[0])
                            + Math.abs(chicken.get(i)[1] - house.get(j)[1]);
                    tmp = Math.min(tmp, distance);
                }
            }
            res += tmp;
        }
        ans = Math.min(res, ans);
        return;
    }

    // 백트래킹
    for (int i = start; i < chicken.size(); i++) {
        pick[i] = true;
        solve(i + 1, cnt + 1);
        pick[i] = false;
    }

	}

	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());
    map = new int[n][n];
    house = new ArrayList<>();
    chicken = new ArrayList<>();
    // System.out.println(n+" "+m);
    for (int i = 0; i < n; i++) {
        // String string = br.readLine();
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < n; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
            if (map[i][j] == 1) {
                house.add(new int[] { i, j });
            } else if (map[i][j] == 2) {
                chicken.add(new int[] { i, j });
            }
        }
        pick = new boolean[chicken.size()];
        ans = Integer.MAX_VALUE;
        // System.out.println(Arrays.deepToString(map));
        solve(0, 0);
    } // 입력받기
    System.out.println(ans);
}//main
}//class