치킨배달 [백준 15686][JAVA][골드 5][조합]

 

[광고 누르면 오늘의 행운 상승!!]

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

15686번: 치킨 배달

조합 문제

1. 참고사항

치킨먹고싶다.

2. 구현

- 전체 치킨집 중 K개를 뽑는다
- 뽑아진 치킨집과 집들을 비교해서 치킨거리를 구한다
- 치킨거리 중 가장 작은 거리를 갱신시킨다.

 

package Study6;

import java.io.*;
import java.util.*;

public class 치킨배달 {
	static int[][] map;
	static boolean[] visit;
	static int N,K,ans = Integer.MAX_VALUE;
	static int chiken;
	static int[] chikenarr;
	static List<int[]> chikenList;
	static List<int[]> home;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		map = new int[N][N];
		home = new ArrayList<>();
		chikenList = new ArrayList<>();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				if(map[i][j] == 1) home.add(new int[] {i,j});
				if(map[i][j] == 2) {
					chikenList.add(new int[] {i,j});
					chiken++;
				}
			}
		}
		
		chikenarr   = new int[K];
		visit = new boolean[chiken];
		comb(0,0);
		
		System.out.println(ans);
	}
	private static void comb(int start, int cnt) {
		if(cnt == K) {
			int chikenDis = 0;
			int min = 0;
			
			for (int i = 0; i < home.size(); i++) {
				min = Integer.MAX_VALUE;
				for (int k = 0; k < K; k++) {
					int dis = Math.abs(home.get(i)[0] - chikenList.get(chikenarr[k])[0])
							+ Math.abs(home.get(i)[1] - chikenList.get(chikenarr[k])[1]);
					
					min = Math.min(min, dis);
				}
				chikenDis += min;
			}
			ans = Math.min(chikenDis, ans);
			return;
		}
		
		for (int i = start; i < chiken; i++) {
			if(!visit[i]) {
				visit[i] = true;
				chikenarr[cnt] = i;
				comb(i, cnt+1);
				visit[i] = false;
			}
		}
	}
}