[BOJ_15686] 치킨 배달 (골드 5)

---

🐾 알고리즘

• 조합으로 폐업할 치킨집과 운영하는 치킨집을 분류한다. 오픈된 치킨집 M개를 골라 그 중에서 치킨 거리가 최소인 경우를 구한다.

---

 

🐾 생각 포인트

• Point class를 선언해서 좌표를 묶음으로 가지고 다니거나, 그 묶음에서 x, y 좌표를 추출할 수 있다.
• 변수가 여러개 등장하므로 헷갈릴 수 있으니 주의할 것!
• 입력받을 때, 2의 값을 가지는 좌표를 치킨집으로 저장한다. (class에 좌표 저장)
• 오픈한 치킨집을 M개 선택해야 하므로, 재귀를 이용한 조합론을 활용해 M개가 되면 치킨 거리를 구하는 메소드를 호출한다.
• 처음에 저장한 치킨집의 좌표를 다시 Class 에서 꺼내준다. 이때, int chicken이 아닌 Point(클래스명) chicken으로 하여, 즉, 클래스명을 타입으로 하여 값을 반환할 수 있도록 한다.
•  

---

🐾 소스코드

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

public class Main {
	static int[][] map;
	static int N;
	static int M;
	static List<Point> chickenhome = new ArrayList<>();
	static int min = Integer.MAX_VALUE;
	static int[] finalopen;

	static class Point {
		int x;
		int y;

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

	}

	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());

		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] == 2) {
					chickenhome.add(new Point(i, j));
				}
			}
		} // 입력완
		/* 치킨집중에서 1개만 선택할 경우, 2개만 선택할 경우 등등 해서 치킨 거리계속 구하기 */
		finalopen = new int[M];
		isOpen(0, 0);

		System.out.println(min);
	}

	// 계속 오픈해 있는 애들 결정하기
	private static void isOpen(int count, int idx) {
		// 기저
		if (count == M) {
			min = Math.min(min, calc_dist());
			return;
		}
		// 재귀
		for (int i = idx; i < chickenhome.size(); i++) {
			finalopen[count] = i;
			isOpen(count + 1, i + 1);
		}

	}

	// 오픈한 m개의 가게 골랐으면 그 때 치킨거리 구하자.
	private static int calc_dist() {
		int sum = 0;

		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (map[r][c] == 1) {
					int minlen = Integer.MAX_VALUE;
					for (int k = 0; k < M; k++) {
						Point chicken = chickenhome.get(finalopen[k]);
						int d = Math.abs(r - chicken.x) + Math.abs(c - chicken.y);
						minlen = Math.min(minlen, d);
					}
					sum += minlen;
				}
			}
		}
		return sum;
	}

}

---

😵‍💫 공부해야 할 점

• 아직 class 를 다루는 게 익숙하지 않다! 
• 조합과 순열, 부분집합 공부하기 !!