[백준] 15686번 : 치킨 배달

문제

15686번: 치킨 배달

 

접근 방식

M개 이상 13개 이하의 치킨집이 있을 때, M개의 치킨집을 골라

가장 적은 치킨 거리를 구해야 한다.

 

입력만 보면 그래프 문제처럼 보이기도 하지만 그래프를 쓸 일은 없다.

 

리스트 두 개를 만들어 입력을 받으면서 집과 치킨집의 좌표를 담아준 후에

두 리스트를 반복문을 돌면서 각 집과 치킨집들의 거리를 모두 구해준다.

 

그 후 백트래킹으로 M개의 치킨집을 고른 후에

선택된 치킨집들과 집들의 치킨 거리를 구한 후

최소 치킨 거리를 비교해 주며 갱신하면 된다.

 

순서가 다른 중복된 조합까지 반복적으로 계산하면

시간초과가 발생하는 문제이기 때문에

중복된 조합을 피해서 백트래킹을 해줘야 한다.

 

풀이

class Main {
    
    static int n, m, h, c, answer = Integer.MAX_VALUE;
	static ArrayList<Pair> home = new ArrayList<>();
	static ArrayList<Pair> chicken = new ArrayList<>();
	static int[] selects;
	static int[][] distance;
	static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < n; j++) {
				int x = Integer.parseInt(st.nextToken());

				if (x == 1) home.add(new Pair(i, j));
				if (x == 2) chicken.add(new Pair(i, j));
			}
		}

		c = chicken.size();
		h = home.size();
		isUsed = new boolean[c];
		selects = new int[m];

		calculateDistance();
		solve(0, 0);

		System.out.println(answer);
	}

	static void calculateDistance() {
		distance = new int[h][c];

		for (int i = 0; i < h; i++) {
			Pair cur = home.get(i);
			for (int j = 0; j < c; j++) {
				Pair tar = chicken.get(j);
				distance[i][j] = Math.abs(cur.x - tar.x) + Math.abs(cur.y - tar.y);
			}
		}
	}

	static void solve(int start, int size) {
		if (size == m) {
			calculateSum();
			return;
		}

		for (int i = start; i < c; i++) {
			if (isUsed[i]) continue;
			isUsed[i] = true;
			selects[size] = i;
			solve(i + 1, size + 1);
			isUsed[i] = false;
		}
	}

	static void calculateSum() {
		int sum = 0;

		for (int i = 0; i < h; i++) {
			int min = Integer.MAX_VALUE;

			for (int j = 0; j < m; j++) {
				min = Math.min(min, distance[i][selects[j]]);
			}

			sum += min;
		}

		answer = Math.min(answer, sum);
	}

	static class Pair {
		int x, y;

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