백준 15686. 치킨배달

🅰 백준 15686. 치킨배달

✏️ **문제 풀이**

• 조합을 이용하여서 모든 케이스 탐색
• LinkedList를 이용하여 문제를 풀었다.
• 전체 치킨집 개수 C 선택된 치킨집 개수(M) 번의 조합을 선택하여 선택된 치킨집 케이스 마다 최소가 되는 치킨거리를 저장하였고
• 조합의 모든 케이스를 돌았을 시 그때 최소가 되는 치킨거리를 선택하였다.

✏️ **소스코드**

package com.ssafy.baekjoon;

import java.util.*;

public class Main_골드5_15686_손은성 {
	static LinkedList<int[]> chicken = new LinkedList<int[]>();
	static LinkedList<int[]> selected_chicken = new LinkedList<int[]>();
	static LinkedList<int[]> house = new LinkedList<int[]>();
	static int N;
	static int M; // 선택된 치킨집 개수
	static int chickenCnt, houseCnt;
	static int map[][];
	static int minLength2 = Integer.MAX_VALUE, sum, minLength = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		map = new int[N][N];

		// 지도 데이터 저장
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = sc.nextInt();
				if (map[i][j] == 1) {
					house.add(new int[] { i, j });
				} else if (map[i][j] == 2) {
					chicken.add(new int[] { i, j });
				}
			}
		}

		chickenCnt = chicken.size();	// 현재 치킨집 개수 
		houseCnt = house.size();		// 현재 집 개수
		comb(0,0);
		System.out.println(minLength2);	// 폐업 후 도시의 최소 치킨거리
	}

	public static void comb(int n, int start) {
		if (n == M) {
			for (int i = 0; i <houseCnt; i++) {  // 집의 수
				for (int j = 0; j < M; j++) {  // 선택된 치킨집 
					// 치킨거리 계산
					int length = Math.abs(house.get(i)[0] - selected_chicken.get(j)[0]) + Math.abs(house.get(i)[1] - selected_chicken.get(j)[1]);
					minLength = Math.min(minLength, length); // 한 집에서 모든 치킨집의 거리 비교 후 치킨거리 저장
				}sum+=minLength; //선택된 모든 치킨거리 계산
				minLength = Integer.MAX_VALUE;
			}
			minLength2 = Math.min(minLength2, sum); // 조합의 모든 케이스 중 최소가 되는 치킨거리 저장
			sum = 0;
			return;
		}
		
		// LinkedList를 이용한 조합 생성
		for (int i = start; i < chickenCnt; i++) {
			selected_chicken.add(n, chicken.get(i));
			comb(n + 1, i + 1);
		}
	}
}

 

✅ 후기

• 순열과 조합, 부분집합을 공부했는데 완전탐색 기법에 있어서 꼭 필요한 부분이라는 생각이 들었다. 더 효율적이고 빠른 코드를 짤 수 있도록 노력해야겠다.