[BOJ] 15686 치킨배달 [Java]

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

15686번: 치킨 배달

---

1. 문제 요약

NxN 크기의 도시에 치킨집, 집이 있다. 집에서 치킨집까지의 거리를 '치킨거리'라고 한다.

치킨집 전체 수 중 M개를 선택하여 각각의 집에 대하여 최소가 되는 치킨거리의 합을 구하여 출력하는 문제다.

 

각각의 집마다 최소가 되는 치킨거리를 구하고, 이를 모두 합하면 된다.

거리는 (a,b) (c,d) 두 칸을 예로들면 |a-b| + |c-d| 로 구한다. (맨하탄 거리 공식)

0 : 빈칸

1 : 집

2 : 치킨집

제약조건은 (M <= 치킨집 <= 13), (2 <= N <= 50),  (집 <= 2N) 이다.

 

2. 풀이

조합 + 구현 문제이다.

1. 입력

먼저 입력받을 때 좌표 값이 1이면 집, 2이면 치킨집 ArrayList에 각각 add 해주었다.

(그 전에, x,y 좌표를 담는 Pos클래스를 생성하여 ArrayList를 Pos으로 생성해주었다.)

 

2. 치킨집 선택 및 치킨 거리 구하기

그 다음 치킨집 M곳을 선택해주기 위해 조합을 사용하였다.

조합 함수 comb의 기저조건에서 check() 함수를 만들어 치킨거리를 구하고, min을 갱신하였다.

 

내가 놓친 부분은 3군데이다.

1) 하나의 집 당 M개 치킨집과의 거리 중 최소가 되는 거리가 치킨거리가 된다는 것

  - 하나의 집 당 M개 치킨집과의 거리의 합을 비교해주고 있었다. '최소가 되는 거리'를 놓쳤다.

2) 하나의 집 당 최소 치킨거리를 구해주어야 하므로, min 초기화가 하나의 집 for문 안에서 초기화돼야 한다는 것

  - min을 for문 밖에서 초기화해줘서 다른집의 min과도 계속 비교하면서 sum을 구하고 있었다.

3) 치킨집 M개를 뽑는데 2개를 뽑고있었던 것..

문제를 한번만 읽고는 이해할 수 없었다. 자꾸 하나씩 놓쳐서 4번은 읽은 것 같다.

3. 문제점

치킨 거리의 mix를 갱신하는 부분에서 가장 헷갈렸다. 

처음에는 M = 2로 박아놓고 조합을 돌려서 자꾸 이상한 답이 나왔다.

M으로 바꾸고 M개의 치킨집과 비교해주니 답이 잘 나왔다.

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_15686_치킨배달 {

	static int N, M, min, size;
	static int[] tgt;
	static int[][] map;
	static List<Pos> home = new ArrayList<> ();
	static List<Pos> chicken = new ArrayList<> ();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		tgt = new int[M];
		map = new int[N][N];
		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) home.add(new Pos(i, j)); //집 좌표 add
				if (map[i][j] == 2) chicken.add(new Pos(i, j)); //치킨집 좌표 add
			}
		} 
		size = chicken.size(); //치킨집 개수
		//입력 끝
		
		//탐색 - 조합
		min = Integer.MAX_VALUE;
		comb(0, 0);
		System.out.println(min);
	}
	
	static void comb(int tgtIdx, int srcIdx) {
		if (tgtIdx == M) { //치킨집 2곳 선택
			check(); //치킨거리 구하고 min 갱신
			return;
		}
		
		if (srcIdx == size) return;
		
		tgt[tgtIdx] = srcIdx;
		
		comb(tgtIdx+1, srcIdx+1);
		comb(tgtIdx, srcIdx+1);
	}
	
	static void check() { //치킨거리
		int sum = 0;
		for (Pos h : home) {
			int min_dist = Integer.MAX_VALUE; //for문 밖에 넣어주면 다른집과의 최소거리도 비교하게 됨
			for (int i = 0; i < M; i++) { //M개 치킨집 중 가장 최소거리 치킨집 찾기
				int dist = Math.abs(chicken.get(tgt[i]).y - h.y) + Math.abs(chicken.get(tgt[i]).x - h.x);
				min_dist = Math.min(dist, min_dist); 
			}
			sum += min_dist; //그 집의 최소 거리만 합해줌
		}
		min = Math.min(sum, min); //전체 조합 중 최소값 갱신
	}
	
	static class Pos {
		int y, x;
		public Pos(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
}