[백준] 15686 : 치킨 배달 - JAVA(자바) - 사좋배 공유

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

15686번: 치킨 배달

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class chicken{
	int x;
	int y;
	int ct;
	chicken(int x, int y, int ct){
		this.x=x;
		this.y=y;
		this.ct=ct;
	}
}
class pos{
	int x;
	int y;
	pos(int x, int y){
		this.x=x;
		this.y=y;
	}
}
public class Main {
	static int size;
	static int count;
	static int [][]arr;
	static ArrayList<Integer>list;
	static int twocount;
	static int [][]initarr;
	static ArrayList<chicken> chickenlist;
	static int[]dx= {-1,0,1,0};
	static int[]dy= {0,1,0,-1};
	static ArrayList<pos>realchickenlist;
	static ArrayList<pos>personlist;
	static int MIN;
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		size =sc.nextInt();
		count=sc.nextInt();
		arr=new int[size][size];
		chickenlist=new ArrayList<chicken>();
		realchickenlist=new ArrayList<pos>();
		personlist=new ArrayList<pos>();
		list = new ArrayList<Integer>();
		int cnt=1;
		twocount=0;
		MIN=Integer.MAX_VALUE;
		for(int i=0;i<size;i++) {
			for(int j=0;j<size;j++) {
				arr[i][j]=sc.nextInt();
				if(arr[i][j]==2) {
					chickenlist.add(new chicken(i,j,cnt++));
					twocount++;
				}
				if(arr[i][j]==1) {
					personlist.add(new pos(i,j));
				}
			}
		}
		//count만큼 뽑아내기
		dfs(1);
		System.out.println(MIN);
	}
	private static void dfs(int index) {
		if(list.size()==count) {
			//배열이 넣기
			init();
			//거리 값 구하기
			int sum=0;
			for(int i=0;i<personlist.size();i++) {
				int min = Integer.MAX_VALUE;
				for(int j=0;j<realchickenlist.size();j++) {
					int dis = Math.abs(personlist.get(i).x-realchickenlist.get(j).x)+Math.abs(personlist.get(i).y-realchickenlist.get(j).y);
					if(dis<min) {
						min=dis;
					}
				}
				sum=sum+min;
			}
			if(sum<MIN) {
				MIN=sum;
			}
			realchickenlist.clear();
		}
		for(int i=index;i<=twocount;i++) {
			list.add(i);
			dfs(i+1);
			list.remove(list.size()-1);
		}
		
	}
	private static void init() {
		initarr=new int[size][size];
		for(int i=0;i<list.size();i++) {
			for(int j=0;j<chickenlist.size();j++) {
				if(list.get(i)==chickenlist.get(j).ct) {
					int x= chickenlist.get(j).x;
					int y= chickenlist.get(j).y;
					realchickenlist.add(new pos(x,y));
				}
			}
		}
	}
}