[백준/자바] 15686 치킨 배달

15686

접근법

어떻게 효율적으로 남길 치킨집을 골라야하나 고민하다 시간을 많이 버림...
결론은 그런 거 없고 가능한 조합 모두 만들어서 가장 치킨 거리가 작아지는 조합을 찾는 게 답이다.

1. 지도를 저장할 때 2차원 배열 대신 (x,y) 좌표로 집과 치킨집 위치를 저장
2. find 함수 = 가능한 모든 조합을 찾는 함수
   • 폐업 시키지 않고 남길 조합이 완성되면 남은 치킨집과 집들 간 거리를 구한다
   • 구한 거리를 배열에 저장
3. 2번을 통해 구한 모든 거리들 중 가장 작은 치킨 거리를 구함

코드

package boj.;


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

public class Test {
	static int N;
	static int M;
	static Position[] store;
	static int[] distance;
	static int minSum = Integer.MAX_VALUE;
	static Position[] result;
	static ArrayList<Position> homes = new ArrayList<>();
	static ArrayList<Position> chickens = new ArrayList<>();
	
	static class Position {
		int x;
		int y;
		Position(int x, int y){
			this.x = x;
			this.y = y;
		}
		@Override
		public String toString() {
			return "Position [x=" + x + ", y=" + y + "]";
		}
	}
	

	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());
		
		store = new Position[M];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int map = Integer.parseInt(st.nextToken());
				if (map == 1) {
					homes.add(new Position(i,j));
				}
				if (map == 2) {
					chickens.add(new Position(i, j));
				}
			}
		}
		distance = new int[homes.size()];
		for (int i = 0; i < homes.size(); i++) {
			distance[i] = Integer.MAX_VALUE;
		}
		
		find(0, 0);
		System.out.println(minSum);
	}
	
	
	static void find(int idx, int targetIdx) {
		if (M == targetIdx) {
			int sum = 0;
			for (int i = 0; i < homes.size(); i++) {
				for (int j = 0; j < M; j++) {
					Position home = homes.get(i);
					Position chicken = store[j];
					int tempDist = Math.abs((home.x - chicken.x)) + Math.abs((home.y - chicken.y));
					distance[i] = Math.min(distance[i], tempDist);
				}
			}
			
			for (int i = 0; i < homes.size(); i++) {
				sum += distance[i];
			}
			minSum = Math.min(minSum, sum);
			for (int i = 0; i < homes.size(); i++) {
				distance[i] = Integer.MAX_VALUE;
			}
			return;
		}
		for (int i = idx; i < chickens.size(); i++) {
			store[targetIdx] = chickens.get(i);
			find(i + 1, targetIdx + 1);
		}
	}
	
}