[BAEKJOON 백준] 15686 치킨 배달

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

15686번: 치킨 배달

 

집과 치킨집과의 거리가 최소로하는 치킨집을 남기는 문제입니다.

 

재귀를 이용해서 남겨둘 치킨집 수만큼 조합을 하고, 남겨진 치킨집을 이용해서 집에서 가까운 치킨집을 찾아 치킨거리를 합하게 됩니다.

 

그리고 그중에서 치킨집거리를 최소로 할 수 있는 치킨집 조합을 선택하고, 최소인 치킨집 거리를 출력하는 문제입니다.

 

import java.util.Scanner;

public class Main {

	static class Point { // 치킨집 위치와 집의 위치를 저장해줄 클래스
		int x, y;

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

	}

	static Point chickenarr[]; // 치킨집 위치
	static Point housearr[]; // 집 위치
	static Point temp[];
	static int cnt, cnt2;
	static int N, M;
	static int result = 99999999;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();
		temp = new Point[M];
		chickenarr = new Point[13];
		housearr = new Point[2 * N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int temp = sc.nextInt();
				if (temp == 2) {
					chickenarr[cnt++] = new Point(i, j); // 입력이 2인 곳을 찾아 치킨집 배열에 넣어줍니다.
				} else if (temp == 1) {
					housearr[cnt2++] = new Point(i, j); // 입력이 1인 곳을 찾아 집 배열에 넣어줍니다.
				}
			}
		}
		solve(0, 0);
		System.out.println(result);
	}

	private static void solve(int count, int start) {
		// TODO Auto-generated method stub
		if (count == M) { // 치킨집 수가 M개가 되면 아래와 같이 집과 치킨집과의 거리를 구하고, 최소값을 찾습니다.
			int answer = 0;
			for (int i = 0; i < cnt2; i++) {
				int no = 9999999;

				for (int j = 0; j < M; j++) { // 집과 치킨집 사이 거리가 가장짧은 치킨집을 찾아 줍니다.
					if (no > Math.abs(housearr[i].x - temp[j].x) + Math.abs(housearr[i].y - temp[j].y)) {
						no = Math.abs(housearr[i].x - temp[j].x) + Math.abs(housearr[i].y - temp[j].y);
					}
				}
				answer += no; // 그거리를 더해줍니다.
			}
			if (result > answer) { // 치킨들과 집들과의 거리가 최소가 되는 값을 찾아줍니다.
				result = answer;
			}
			return;
		}

		for (int i = start; i < cnt; i++) {
			temp[count] = chickenarr[i];
			solve(count + 1, i + 1);
		}
	}

}