[백준] 15686 치킨 배달 - JAVA

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

public class Main {

	static int N, M, map[][], answer = Integer.MAX_VALUE;
	static ArrayList<Pos> bbq = new ArrayList<Pos>(), house = new ArrayList<Pos>();

	static class Pos {
		int x;
		int y;

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.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(in.readLine());
			for (int j = 0; j < N; j++) {
				int temp  = Integer.parseInt(st.nextToken());
				map[i][j] = temp;
				if(temp == 1) {
					house.add(new Pos(j, i));
				}else if(temp == 2) {
					bbq.add(new Pos(j, i));
				}
			}
		}
		chicken(0, 0, 0);
		System.out.println(answer);
	}

	public static void chicken(int cnt, int start, int flag) {
		if (cnt == M) {
			// 계산
			int[] value = new int[house.size()];
			for (int i = 0; i < value.length; i++) {
				value[i] = Integer.MAX_VALUE;
			}
			for (int i = 0; i < bbq.size(); i++) {
				if((flag & 1<<i) != 0) {
					Pos ck = bbq.get(i);
					for (int j = 0; j < house.size(); j++) {
						Pos h = house.get(j);
						int dist = Math.abs(ck.x - h.x) + Math.abs(ck.y - h.y);
						value[j] = Math.min(value[j], dist);
					}
				}
			}
			int total = 0;
			for (int d : value) {
				total += d;
			}
			answer = Math.min(total, answer);
			return;
		}

		for (int i = start; i < bbq.size(); i++) {
			if((flag & 1<<i) == 0) {
				chicken(cnt+1, i+1, flag | 1<<i);
			}
		}
	}

}

1. 문제 유형 : 조합

2. 시간복잡도 : O(xCm*MN) : 치킨 집 x개 중 M개 선택(조합), 거리 계산(2MN)