[BOJ/Java] 15686 : 치킨 배달

문제

 

 

 

풀이

 

• 설계

어제 풀었던 최적경로 문제와 비슷해서인지 특별한 문제 없이 풀 수 있었다 / 사실 bfs 써서 가까운 치킨집을 찾으려다가 어차피 폐업시키지 않을 치킨집 최대 개수가 13이라 모두 비교했다

 

 

 

코드

 

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

public class Main { // 치킨 배달
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] map;
	static int N, M;
	static ArrayList<Node> home = new ArrayList<>();
	static ArrayList<Node> chicken = new ArrayList<>();
	static int[] combArr;
	static int ans = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(in.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 1; j <= N; j++) {
				char temp = st.nextToken().charAt(0);
				if (temp == '1') {
					home.add(new Node(i, j));
				} else if (temp == '2') {
					chicken.add(new Node(i, j));
				}
			}
		}
		combArr = new int[M];
		combination(0, 0);
		System.out.println(ans);
	}

	private static void combination(int cnt, int start) {
		if (cnt == M) {
			ans = Math.min(ans, calculation(combArr));
			return;
		}
		for (int i = start; i < chicken.size(); i++) {
			combArr[cnt] = i;
			combination(cnt + 1, i + 1);
		}

	}

	private static int calculation(int[] combArr) {
		int sum = 0;
		for (Node h : home) {
			int dist = Integer.MAX_VALUE;
			for (int index : combArr) {
				dist = Math.min(dist, Math.abs(h.x - chicken.get(index).x) + Math.abs(h.y - chicken.get(index).y));
			}
			sum += dist;
		}
		return sum;
	}

	static class Node {
		int x, y;

		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}