[백준] 치킨배달

package Solution;
/*
*문제풀다가 치킨배달시켜먹게 도와준 문제
*home, chick 를 arraylist로 관리 
*백트래킹구현
*/
import java.util.ArrayList;

import java.util.Scanner;

public class 치킨배달 {
	static int N, M,ans; 
	static int map[][];
	static boolean[] visited;
	static ArrayList<Node> home;
	static ArrayList<Node> chick;
	
	
	static class Node {
		int x; 
		int y;
		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt(); // 치킨집을 고른수 
		map = new int[N][N];
		home = new ArrayList<>();
		chick = new ArrayList<>();
		
		for(int i =0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j] ==1) {
					home.add(new Node(i,j));
				}else if(map[i][j] ==2) {
					chick.add(new Node(i,j));
				}
			}
		}
		
		ans = Integer.MAX_VALUE;
		visited = new boolean[chick.size()];

		dfs(0,0);
		
		System.out.println(ans);
	}

	private static void dfs(int start, int cnt) {
		if(cnt == M) {
		int res = 0;
		for(int i =0; i<home.size(); i++) {
			int temp = Integer.MAX_VALUE;
			
			for(int j=0; j<chick.size(); j++) {
				if(visited[j]) {
					int dis = Math.abs(home.get(i).x - chick.get(j).x) + Math.abs(home.get(i).y - chick.get(j).y);
					temp = Math.min(temp, dis);
				}
			}
			res += temp;
		}
		ans = Math.min(ans, res);
		return;
		}
		
		//구현부
		for(int i=start; i<chick.size(); i++) {
			visited[i] = true;
			dfs(i+1, cnt+1);
			visited[i] = false;
		}
	}


	
}