[BOJ] 15686 치킨 배달

 

 

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int m,result = Integer.MAX_VALUE;
	static boolean[] visit;
	static List<int[]> houses,stores;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int[][] map = new int[n][n];
		houses = new ArrayList<>();
		stores = new ArrayList<>();
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j]==1) houses.add(new int[] {i,j});
				if(map[i][j]==2) stores.add(new int[] {i,j});
			}
		}
		visit = new boolean[stores.size()];
		dfs(0,0);
		System.out.println(result);
	}
	private static void dfs(int idx,int cnt) {
		if(cnt==m) {
			int total = 0;
			for(int i=0;i<houses.size();i++) {
				int min = Integer.MAX_VALUE;
				for(int j=0;j<stores.size();j++) {
					if(visit[j]) {
						int dist = Math.abs(houses.get(i)[0] - stores.get(j)[0])
								+ Math.abs(houses.get(i)[1] - stores.get(j)[1]);
						min = Math.min(min, dist);
					}
				}
				total += min;
			}
			result = Math.min(result, total);
			return;
		}
		for(int i=idx;i<stores.size();i++) {
			if(!visit[i]) {
				visit[i] = true;
				dfs(i+1,cnt+1);
				visit[i] = false;
			}
		}
	}
}