[백준/java] 15686번: 치킨 배달 - 삼성 SW 역량테스트 기출(조합문제)

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

15686번: 치킨 배달

백준 15686번 치킨 배달

치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

 

쉬운 말로,

 

집 A가 있고, 치킨집 B, C ,D가 있다 가정하면,

 

집 A부터 B까지의 거리, A부터 C까지의 거리, A부터 D까지의 거리를 누적하면 도시의 치킨 거리의 합이 구해진다.

 

이 과정을 모든 집 마다의 치킨 거리를 구하여 가장 적은 값을 구하면 된다.

 

combi 함수는 치킨집의 조합을 구하여 m개의 치킨집의 조합이 구해졌을 때,

 

각 집마다 모든 치킨집과의 거리를 누적하여 치킨 거리 값을 구한 후, 최소값을 구한다.

 

package combination;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class P15686_ChickenDelivery {
	static int[][] map;
	static int[] check;
	static int n, m, len, answer = Integer.MAX_VALUE;
	static List<Point> chicken = new ArrayList<Point>();
	static List<Point> home = new ArrayList<Point>();
	static class Point {
		int y, x;
		Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) {
		init();
		combi(0,0);
		System.out.println(answer);
	}
	
	public static void combi(int L, int s) {
		if(L == m) {
			int sum = 0;
			for(Point p : home) {
				int dis = Integer.MAX_VALUE;
				for (int x : check) {
					dis = Math.min(dis, Math.abs(p.x - chicken.get(x).x) 
                 	 				  	+ Math.abs(p.y - chicken.get(x).y));
				}
				
				sum += dis;
			}
			
			answer = Math.min(answer, sum);
		} else {
			for (int i = s; i < len; i++) {
				check[L] = i;
				combi(L+1, i+1);
			}
		}
	}
	
	public static void init() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt(); m = sc.nextInt();
		map = new int[n][n];
		check = new int[m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int tmp = sc.nextInt(); 
				map[i][j] = tmp;
				if(tmp == 1) home.add(new Point(i,j));
				else if(tmp == 2) chicken.add(new Point(i,j));
			}
		}
		
		len = chicken.size();
	}
}