[백준/boj] 15686: 치킨 배달 (Java) / 조합 / 브루트포스

문제

15686번: 치킨 배달

풀이

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

public class Main {
	static BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M;
	static List<int[]> chicken, house;
	static int total =0, capitalChickenDir = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws Exception {
		input();
		combination(0, 0, new int[M][2]);
		System.out.println(capitalChickenDir);
	}
	
    // 주어진 치킨 집 개수에서 M개를 골라내는 조합
	private static void combination(int cnt, int start, int[][] nums) { 
		if(cnt == M) {
			calcDiff(nums); // 조합이 생성될 때 마다 거리 계산을 실행한다.
            // 조합이 생성될 때마다 도시의 치킨 거리를 최솟값으로 갱신
			capitalChickenDir = Math.min(capitalChickenDir, total); 
			total = 0; // 도시의 치킨 거리 초기화
			return;
		}
		
		for(int i= start; i< chicken.size(); i++) {
			nums[cnt] = chicken.get(i);
			combination(cnt+1, i+1, nums);
		}
	}

	private static void calcDiff(int[][] nums) {
		int chickenDir = Integer.MAX_VALUE;  // 한 집의 치킨 거리 초기화
		for(int i=0 ; i < house.size(); i++) {
			chickenDir = Integer.MAX_VALUE;
			int hx = house.get(i)[0];
			int hy = house.get(i)[1];
            // 치킨집의 좌표를 하나씩 빼오면서
			for(int[] chickenPos : nums) { 
            	// 한 집의 치킨 거리 최솟값으로 갱신
				chickenDir = Math.min(chickenDir, 
                Math.abs(hx-chickenPos[0])+Math.abs(hy - chickenPos[1])); 
			}
			total+= chickenDir; // 도시의 치킨 거리에 한 집의 치킨 거리를 더한다. 
		}
	}

	private static void input() throws Exception {
		st = new StringTokenizer(br.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		chicken = new ArrayList<int[]>();
		house = new ArrayList<int[]>();
		for(int i=1; i<=N; i++) { // 좌표 인덱스는 1부터 N까지 (행)
			st =new StringTokenizer(br.readLine());
			for(int j=1; j<=N; j++) { // 좌표 인덱스는 1부터 N까지 (열)
				int input = stoi(st.nextToken()); 
				if(input == 1) house.add(new int[] {i,j}); // 1이면 house 배열에 add
				else if(input == 2) chicken.add(new int[] {i,j}); // 2면 chicken 배열에 add
			}
		}
	}
	
	private static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

 

조합 코드가 이해 안된다면 아래 포스팅을 참고하면 좋다. 

2021/02/15 - [언어/자바(Java)] - [Java] 순열 / 조합 / 부분 집합 정리 (수도 코드 - 재귀편)

[Java] 순열 / 조합 / 부분 집합 정리 (수도 코드 - 재귀편)