백준 15686 : 치킨 배달

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

15686번: 치킨 배달

[ 문제풀이 ]

치킨집 중에 M 개를 선택해서 가능한 모든 경우의 수를 탐색하는 완전 탐색 문제이다. 조합 함수를 구현할 수만 있다면 쉽게 해결할 수 있을 것이다.

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

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	
	static int N, M, answer;
	static int[][] map;
	static List<Node> chickens, homes, picks;
	
	static class Node {
		int y, x;
		
		public Node(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		answer = (int)1e9;
		map = new int[N][N];
		chickens = new ArrayList<>();
		homes = new ArrayList<>();
		picks = 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) homes.add(new Node(i, j));
				if (map[i][j] == 2) chickens.add(new Node(i, j));
			}
		}
		
		selectChicken(0);
		
		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}
	
	//모든 치킨집 중에서 M개를 선택하는 조합 함수
	public static void selectChicken(int idx) {
		if (picks.size() == M) {
			answer = Math.min(answer, getDistance());
			return;
		}
		
		for (int i = idx; i < chickens.size(); ++i) {
			picks.add(chickens.get(i));
			selectChicken(i + 1);
			picks.remove(picks.size() - 1);
		}
	}
	
	//모든 집을 선택된 치킨집과의 거리를 계산하여 최솟값을 구함
	public static int getDistance() {
		int totalDist = 0;
		
		for (Node home : homes) {
			int minDist = (int)1e9;
			
			for (Node chicken : picks) {
				minDist = Math.min(minDist, Math.abs(home.y - chicken.y) + Math.abs(home.x - chicken.x));
			}
			
			totalDist += minDist;
		}
		
		return totalDist;
	}
}