[Baekjoon] 백준 15686 치킨 배달 (G5 / 조합) - Java

링크

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

15686번: 치킨 배달

 

 

 

문제 해석

- 입력
첫 번째 줄 : N M # 도시크기, 살아남을 치킨집 개수
나머지 줄 : N줄을 통해 도시의 거리 정보 전달

0 : 빈칸
1 : 집
2 : 치킨집

치킨 거리 계산 방법 : |R1 - R2| + |R1 - R2|

전체 치킨집 중 M개의 치킨집만을 유지한다고 했을 때, 모든 집의 치킨거리가 최소가 되는 값을 구하라.

 

 

 

코드

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

public class Main2 {
	static ArrayList<int[]> chicken;
	static ArrayList<int[]> home;
	static int answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		chicken = new ArrayList<>();
		home = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int now = Integer.parseInt(st.nextToken());

				if (now == 1) {
					home.add(new int[] { i, j });
				}

				if (now == 2) {
					chicken.add(new int[] { i, j });
				}
			}
		}
		answer = Integer.MAX_VALUE;
		recursive(new int[M], 0, 0);
		System.out.println(answer);

	}

	private static void recursive(int[] sel, int aIdx, int sIdx) {
		// basis part
		if (sel.length == sIdx) {
			int eachRecursiveDistance = 0;
			// 각 집마다 치킨 가게까지의 거리를 계산하여 가장 짧은 치킨 가게 선정
			for (int j = 0; j < home.size(); j++) { // 집 선택
				int eachHomeDistance = Integer.MAX_VALUE;
				for (int i = 0; i < sel.length; i++) { // 치킨 가게 선택
					int nowHomeDistance = Math.abs(chicken.get(sel[i])[0] - home.get(j)[0])
							+ Math.abs(chicken.get(sel[i])[1] - home.get(j)[1]);

					eachHomeDistance = Math.min(eachHomeDistance, nowHomeDistance);
				}
				eachRecursiveDistance += eachHomeDistance;
			}
			answer = Math.min(answer, eachRecursiveDistance);
			return;
		}

		// inductive part
		for (int i = aIdx; i < chicken.size(); i++) {
			sel[sIdx] = i;
			recursive(sel, i + 1, sIdx + 1);
		}
	}
}

 

 

 

코드 해석

치킨 집 중에서 M개를 골라야하고, 중복이 없고, 순서가 없으므로 조합 문제입니다.

 

거리를 구하는 문제여서 BFS로도 볼 수 있었겠지만 거리를 구하는 공식이 별도로 주어지므로, BFS가 아닌 조합으로 나온 결과를 공식을 통해 계산해야 합니다.

 

 

 

발생한 문제 & 해결 방안

기본적으로 들어가는 arr[]이 일차원 배열이 아니라 ArrayList였기 때문에 sel[]에  단순히 인덱스를 저장했었는데, 이를 사용 시  sel[i]로 하지 않고 i로 하여 값이 이상하게 나왔다.

-> 코드를 잘 작성하자!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice