[백준] 치킨 배달 15686 - JAVA

문제

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

15686번: 치킨 배달

풀이

백트래킹 문제

 

백트래킹에서 가장 중요한 것은 가지치기이다.

이 문제에서는 가지치기를 start를 매개변수로 사용해서 수행한다.

즉, for문을 돌때 백트래킹을 하게 되면 이전 요소들은 이미 수행되었기 때문에 다음 요소에 대해서 백트래킹을 하면 된다. 따라서, start를 매개변수로 하여 가지치기를 수행한다.

 

선정한 치킨집이 M개가 되었다면 visited 배열에는 M개 만큼 true가 되어있을 것이다.

집 좌표 리스트와 치킨집 리스트를 이중 for문을 사용하고 visited 가 true일 때 각각의 집에서 가장 가까운 치킨집을 구하고 그 거리를 모두 더해서 도시의 치킨거리를 구한다.

min 함수를 사용해서 도시의 치킨거리의 최솟값을 구한다.

코드

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

public class Main {
	
	static int min = Integer.MAX_VALUE;
	static int n, m;
	static List<Point> chicken = new ArrayList<>();
	static List<Point> house = new ArrayList<>();
	static boolean visited[];
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
				
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < n; j++) {
				int val = Integer.parseInt(st.nextToken());
				
				if(val == 1)
					house.add(new Point(i, j));
				if(val == 2) {
					chicken.add(new Point(i, j));
				}
			}
		}
		
		visited = new boolean [chicken.size()];

		back(0, 0);
	
		System.out.print(min);
	}
	
	static void back(int count, int idx) {
		if(count == m) {
			int arr [] = new int [house.size()];
			Arrays.fill(arr, Integer.MAX_VALUE);
			
			for(int i = 0; i < chicken.size(); i++) {
				if(visited[i]) {
					Point cPoint = chicken.get(i);
					
					for(int h = 0; h < house.size(); h++) {
						Point hPoint = house.get(h);
						
						int distance = Math.abs(cPoint.r - hPoint.r) + Math.abs(cPoint.c - hPoint.c);
						
						if(arr[h] > distance)
							arr[h] = distance;
					}

				}
					
			}
			
			int sum = 0;
			for(int i=0;i<house.size();i++) {
				sum += arr[i];
			}
			min = Math.min(min, sum);
			return;
		}
		
		for(int i = idx; i<chicken.size();i++) {
			visited[i] = true;
			back(count+1, i + 1);
			visited[i] = false;
		}
		
		
	}
	
	static class Point {
		int r;
		int c;
		
		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
		
	}
	   
}