[JAVA]백준 15686. [G5]치킨 배달

백준 15686. 치킨 배달

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

15686번: 치킨 배달

 

풀이 과정

1. 집과 치킨집의 좌표를 각각 houseList와 chickenList에 저장

2. 치킨집 M개를 뽑은 다음 이중 포문을 이용해서 치킨 거리의 최소합을 계산

3. 탐색을 시작하는 지점이 chickenList의 사이즈를 초과하면 탐색을 종료

 

전체 코드

import java.util.*;

public class Main {

	static int n, m;
	static int[][] board;
	static int min = Integer.MAX_VALUE;
	static ArrayList<Point> chickenList = new ArrayList<>(); // 치킨집 위치를 저장하는 리스트
	static ArrayList<Point> houseList = new ArrayList<>(); // 집의 위치를 저장하는 리스트
	static boolean[] chickenVisited; // 뽑은 치킨집 체크

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		n = scan.nextInt();
		m = scan.nextInt();

		board = new int[n][n];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				board[i][j] = scan.nextInt();
				if(board[i][j] == 1) houseList.add(new Point(i, j));
				else if(board[i][j] == 2) chickenList.add(new Point(i, j));
			}
		}

		chickenVisited = new boolean[chickenList.size()];
		backtracking(0, 0); //m개의 치킨집을 뽑는다.
		System.out.println(min);
	}

	public static void backtracking(int count, int idx) {
		if(count == m) { //치킨 거리의 최솟값을 구한다.
			int total = 0; // 도시의 치킨거리
			for (Point node : houseList) {
				int sum = Integer.MAX_VALUE;
				for (int j = 0; j < chickenList.size(); j++) {
					if (chickenVisited[j]) { //i번째 집에서부터 j번짜 치킨집 까지의 거리 중 최소값을 구한다.
						int dist = Math.abs(node.x - chickenList.get(j).x)
							+ Math.abs(node.y - chickenList.get(j).y);
						sum = Math.min(sum, dist);
					}
				}
				total += sum;
			}
			min = Math.min(total, min);
			return;
		}

		for(int i = idx; i < chickenList.size(); i++) {
			if(!chickenVisited[i]) {
				chickenVisited[i] = true;
				backtracking(count + 1, i + 1);
				chickenVisited[i] = false;
			}
		}
	}

	public static class Point {
		int x;
		int y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}