[백준15686] 치킨 배달 - 자바(JAVA)

1. 문제

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

15686번: 치킨 배달

 

2. 풀이

백트래킹과 DFS를 사용해서 문제를 풀었다.

백트래킹을 적용하지 않으면 시간 초과가 난다. 이것 때문에 살짝 헤맸다.

 

DFS로 탐색하면서 open이라는 boolean 배열에 오픈할 치킨집을 true로 만들어 준다.

cnt가 M과 같아지면 탐색을 종료하고 각 집에서 치킨거리를 모두 더해서 결과값을 만든다.

 

3. 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int N,M;
	static int[][] chicken_dis;
	static ArrayList<Point> home,chicken;
	static boolean[] open;
	static int result;
	
	static class Point {
		int x; // col
		int y; // row
		Point (int x,int y){
			this.x=x;
			this.y=y;
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		
		N=sc.nextInt();
		M=sc.nextInt();
		
		
		
		home=new ArrayList<>();
		chicken=new ArrayList<>();
		
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				int tmp=sc.nextInt();
				if(tmp==1) {
					home.add(new Point(j,i));
				}
				else if(tmp==2) {
					chicken.add(new Point(j,i));
				}
			}
		}
	
		chicken_dis=new int[home.size()][chicken.size()];
		
		for(int i=0;i<home.size();i++) {
			for(int j=0; j<chicken.size();j++) {
				chicken_dis[i][j]=Math.abs(home.get(i).x-chicken.get(j).x)+Math.abs(home.get(i).y-chicken.get(j).y);
			}
		}
		
		open=new boolean[chicken.size()];
		result=Integer.MAX_VALUE;
		dfs(0,0);
		
		System.out.println(result);
	}
	
	public static void dfs(int start, int cnt) {
		if(cnt==M) {
			int sum=0;
			
			for(int i=0;i<home.size();i++) {
				int min=Integer.MAX_VALUE;
				for(int j=0; j<chicken.size();j++) {
					if(open[j]) {
						min=Math.min(min, chicken_dis[i][j]);
					}
				}
				sum+=min;
			}
			result=Math.min(result, sum);
			return;
		}
		
		for(int i=start;i<chicken.size();i++) {
			if(!open[i]) {
				open[i]=true;
				dfs(i+1,cnt+1);
				open[i]=false;
			}
		}
		
	}
	
}