[백준 15686] 치킨 배달

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

 

*M개의 조합 구하기 > bfs 백트래킹으로 구현

//백준 연습
import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static int[][] city;
	
	static class Node{
		int x, y; // 좌표값
		
		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	// 집, 치킨 집 저장할 리스트
	static ArrayList<Node> house_list = new ArrayList<>();
	static ArrayList<Node> chicken_list = new ArrayList<>();
	
	// 결과 저장
	static int result = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		city = new int[N][N];
		
		// 도시 상태 입력받기
		for(int i=0; i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N;j++) {
				city[i][j] = Integer.parseInt(st.nextToken());
				if(city[i][j] == 2) {	// 치킨집일 경우
					chicken_list.add(new Node(i, j));
				}
				else if(city[i][j] == 1) {
					// 집일 경우
					house_list.add(new Node(i, j));
				}
			}
		}
		
		// M개의 치킨집 고르기
		dfs(0, new ArrayList<>());
		
		// 결과 출력
		System.out.println(result);
		
	} //main
	
	// M개의 치킨집 고르기 > dfs 이용
	static void dfs(int start, ArrayList<Node> selected) {
		if(selected.size() == M) {
			int total_distance = getChickenDistance(selected);
			result = Math.min(result, total_distance);
			return;
		}
		
		for(int i=start; i<chicken_list.size(); i++) {
			selected.add(chicken_list.get(i));
			dfs(i+1, selected);
			selected.remove(selected.size()-1);
		}
	}
	
	// 치킨 거리 구하기
	static int getChickenDistance(ArrayList<Node> selected) {
		int d = 0; // 거리 저장
		for(Node h : house_list) {
			int minDist = Integer.MAX_VALUE;
			for(Node c : selected) {
				int dist = (Math.abs(h.x-c.x) + Math.abs(h.y-c.y));
				minDist = Math.min(minDist, dist);
			}
			d+=minDist;
		}
		
		return d;
	}

}