[백준 - JAVA] 치킨 배달

15686번: 치킨 배달

 

문제를 풀기 시작하자마자 치킨이 먹고 싶어져서,

스터디원들과 30분만에 풀고 다같이 치맥을 먹으러 갔던 문제  ◝(⁰▿⁰)◜ 

M이 13이하의 수이기 때문에 기초적인 조합을 구현할 수 있다면 풀 수 있다!

 

풀이 방법

1. 입력을 받으면서, 치킨집과 집의 좌표를 리스트에 각각 저장한다.

2. 치킨집의 리스트로 dfs를 이용한 조합을 구현한다. 
   1. boolean형 배열을 이용해서 중복 처리를 한다.
   2. 치킨집을 M개 골랐을 때 도시의 치킨거리를 구한다.
      
      M개의 치킨집 중 각각의 집에서 가장 가까운 거리를 구해 합한 다음, 
      기존까지 구한 도시의 치킨거리와 비교하여 더 작은 값을 저장한다. 

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

public class Main {

	public static int[][] map;
	public static int N, M, min;
	public static List<int[]> chicken, house, mList;
	public static boolean[] v;

	public static void pick(int index, int cnt) {
		if (cnt == M) {
			int sum = 0; 
			for (int[] h : house) {
				int dis = Integer.MAX_VALUE;
				for (int[] arr : mList) {
					dis = Math.min(dis, Math.abs(arr[0]-h[0])+Math.abs(arr[1]-h[1]));
				}
				sum+=dis;
				if (sum > min)
					return;
			}
			min = Math.min(min, sum);
			return;
		}

		for (int i = index; i < chicken.size(); i++) {
			if (!v[i]) {
				v[i] = true;
				mList.add(chicken.get(i));
				pick(i + 1, cnt + 1);
				mList.remove(cnt);
				v[i] = false;
			}
		}

	}

	public static void main(String[] args) throws Exception {
		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];
		chicken = new ArrayList<int[]>();
		house = new ArrayList<int[]>();
		mList = new ArrayList<int[]>();
		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)
					house.add(new int[] { i, j });
				else if (map[i][j] == 2)
					chicken.add(new int[] { i, j });
			}
		}

		min = Integer.MAX_VALUE;
		v = new boolean[chicken.size()];
		pick(0, 0);
		
		System.out.println(min);
	}

}