15686 치킨 배달 - 삼성 sw 역량 기출

치킨배달

입력 받을 때 List<int[]> 를 사용하여 집과 치킨집의 좌표를 각각 저장

​

1.치킨집과 집과의 거리를 구하는 getDistance함수 구현 - Math라이브러리 사용

​

2.집 하나에서 가장 가까운 치킨집과의 거리를 구하는 calMinDistance함수 구현

현재 집의 좌표를 받아서 모든 치킨집 리스트를 돌면서 최소값 리턴

​

3.남을 치킨집의 모든 경우를 구할 power함수 구현

남을 치킨집의 정수배열 리스트를 생성

cnt와 idx를 들고다니면서 idx는 현재 치킨집의 index, cnt는 남을 치킨집을 뽑았으면 증가

치킨집을 M만큼 뽑았으면 뽑은 리스트로 모든 집에서 치킨집의 거리 최소값을 더하고 리턴

만약 idx가 총치킨집리스트사이즈와 같으면 리턴

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

public class Main치킨배달 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st1.nextToken());
		int M = Integer.parseInt(st1.nextToken());

		int[][] map = new int[N][N];

		home = new ArrayList<>();
		chicken = new ArrayList<>();

		for(int i = 0; i < N; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st2.nextToken());
				if(map[i][j]==1) {
					home.add(new int[] {i,j});
				}else if(map[i][j]==2) {
					chicken.add(new int[] {i,j});
				}
			}
		}
		ans = Integer.MAX_VALUE;
		power(new ArrayList<>(), M, 0, 0);
		System.out.println(ans);

	}
	static int ans;
	static List<int[]> chicken;
	static List<int[]> home;
	static void power(List<int[]> remain, int M, int idx, int cnt) {
		if(cnt == M) {
			int sum = 0;
			for(int i = 0; i < home.size(); i++) {
				sum+=calMinDistance(home.get(i)[0], home.get(i)[1], remain);
			}

			ans = Math.min(ans, sum);
			return;
		}

		if(idx == chicken.size()) {
			return;
		}

		remain.add(new int[] {chicken.get(idx)[0], chicken.get(idx)[1]});
		power(remain, M, idx+1, cnt+1);
		remain.remove(remain.size()-1);
		power(remain, M, idx+1, cnt);

	}

	static int calMinDistance(int hy, int hx, List<int[]> chicken) {
		int min = Integer.MAX_VALUE;
		for(int i = 0; i < chicken.size(); i++) {
			min = Math.min(min, getDistance(hy, hx, chicken.get(i)[0], chicken.get(i)[1]));
		}
		return min;
	}

	static int getDistance(int hy, int hx, int cy, int cx) {
		return Math.abs(hy-cy)+Math.abs(hx-cx);
	}
}