[백준 / Java] 15686번: 치킨 배달 (골드5)

문제 풀이 날짜: 2023.08.11
포스트 작성일: 2023.08.21

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 15686번: 치킨 배달 (골드5)

 

키워드

완전 탐색, 백트래킹

 

풀이 접근법

• 전체 치킨집 중, 순서에 상관 없이 M개를 뽑는다. (조합)
  • Next Permutation으로 풀면 재귀보다 시간을 더 줄일 수 있다.
  • 배열의 0은 선택되지 않은 것이고, 1은 선택되었음을 나타낸다.
  • 문제에 조금 헷갈리게 적혀있는데, 최대 M개라고 해서 1~M개를 다 뽑아보라는 게 아니라 M개만 뽑아도 된다.
• List에 집의 좌표와 치킨집의 좌표를 모두 취합한다.
  • 이렇게 좌표를 취합한 뒤 순회하는 게 Matrix를 순회하는 것보다 공간을 적게 차지한다. (희소 그래프)
• 조합으로 M개의 치킨집을 선정하고, 각 집으로부터 모든 치킨집까지의 거리를 구한다.
  • 치킨집까지의 최소 거리를 구하고, 매 시도마다 sum에 합한다.
  • sum을 구할 때마다 최솟값을 찾는다.

 

코드

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {

	private static int N;
	private static int R;
	private static int answer = Integer.MAX_VALUE;
	
	private static List<Point> houses = new ArrayList<>();
	private static List<Point> stores = new ArrayList<>();
	
	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());
		R = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j = 0; j < N; j++) {
				int input = Integer.parseInt(st.nextToken()); 
				
				if(input == 1) {
					houses.add(new Point(j, i));
				}
				
				if(input == 2) {
					stores.add(new Point(j, i));
				}
			}
		}
		
		int len = stores.size();
		int[] p = new int[len];
		
		for(int i = 0; i < R; i++) {
			p[len - 1 - i] = 1;
		}
		
		do {
			for(int i = 0; i < len; i++) {
				if(p[i] == 0) continue;
				
				answer = Math.min(calculateDist(p), answer);
			}
		} while(np(p));
		
		System.out.println(answer);
	}

	private static int calculateDist(int[] p) {
		int sum = 0;
		for(Point house : houses) {
				int minDist = Integer.MAX_VALUE;
				for(int k = 0; k < p.length; k++) {
					if(p[k] == 0) continue;
					
					Point store = stores.get(k);
					
					int d = Math.abs(house.y - store.y) + Math.abs(house.x - store.x);
					minDist = Math.min(d, minDist);
				}
				sum += minDist;
		}
		
		return sum;
	}

	private static boolean np(int[] p) {
		int N = p.length;
		
		int i = N - 1; //맨 뒤에서 출발
		while(i > 0 && p[i - 1] >= p[i]) --i;
		
		if(i == 0) //이미 마지막 순열임
			return false;
		
		int j = N - 1; //맨 뒤에서 출발
		while(p[i - 1] >= p[j]) --j;
		
		swap(p, i - 1, j);
		
		int k = N - 1; //맨 뒤에서 출발
		while(i < k) { //i, k가 양 끝의 수를 가리킴
			swap(p, i++, k--);
		}
		
		return true;
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

---

백트래킹의 심화 문제이다. Matrix에 담긴 정보를 조합으로 뽑아야 하기 때문에 Matrix 그대로 두고 재귀를 돌기에는 무리가 있다. 별개의 배열이나 리스트로 뽑아서 조합(또는 순열)을 만드는 것이 좋다.

 

git 링크

(git 링크 첨부)