백준 15686번 : 치킨 배달 (JAVA)

DFS를 이용한 문제풀이이다. 

package DFS;

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

class Point {
	int x;
	int y;
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}
public class Baekjoon15686 {
	
	static int N; // 기준 열,행 
	static int M; // 도시에서 치킨 집을 open 할 수 있는 최대 개수 
	static int map[][]; // 초기 값을 담아주기 위한 map 배열
	static ArrayList<Point> home = new ArrayList<>(); // 값이 1이면 집으로 판단하여 home List에 담는다. 
	static ArrayList<Point> chicken = new ArrayList<>(); // 값이 2이면 치킨집으로 판단하여 chicken집 List에 담는다.
	static int []chickenOpenList; // BackTracking을 하기위한  OpenList 
	static int ans = Integer.MAX_VALUE;
	
	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]; 
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int j=0;
			while(st.hasMoreTokens()) {
				map[i][j]= Integer.parseInt(st.nextToken());
				j++;
			}
		}
		
		int chickenOpenNum = 0; // chicken을 처음 선언시 Open 사용자가 입력한 총 치킨 집의 개수를 담는 변수
		
		// 치킨집, 집 각각의 List에 담아주는 로직 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j]==1) home.add(new Point(i+1, j+1));  
				else if(map[i][j] == 2) {
					chicken.add(new Point(i+1, j+1)); 
					chickenOpenNum++;
				}
			}
		}
		
		chickenOpenList = new int[chickenOpenNum];  
		Arrays.fill(chickenOpenList,0);
		
		DFS(0,0);
		System.out.println(ans);
		br.close();
	}
	public 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 < chicken.size(); j++) {
					if(chickenOpenList[j] == 1) {
						int distance = Math.abs(home.get(i).x - chicken.get(j).x) + Math.abs(home.get(i).y - chicken.get(j).y);
						temp = Math.min(temp,distance);
					}	 
				}
				res += temp;
			}
			ans = Math.min(ans, res); 
			return;
		}
		for(int i=start; i<chicken.size(); i++) {
			chickenOpenList[i] = 1;
			DFS(i+1, cnt+1);
			chickenOpenList[i]=0;
		}
	}
}

자세한 설명은 추후에 작성.