[백준.G5] - 15686. 치킨 배달

Jimin Kwon·2025년 9월 21일

백준

알고리즘

목록 보기

7/13

🏆 알고리즘 문제 풀이

📌 문제 정보

문제명 : 치킨 배달
출처 : https://www.acmicpc.net/problem/15686
난이도 : G5
유형 : 백트래킹 / 구현

🧐 문제 설명

문제에서 도시의 치킨 거리를 최소화하는 것이 목표

집과 치킨집이 존재하는 N x N 크기의 도시가 주어진다.
임의의 두 칸 (r1, c1), (r2, c2) 사이의 거리는 |r1 - r2| + |c1 - c2| (맨해튼 거리)이다.
치킨 거리: 특정 집과 가장 가까운 치킨집 사이의 거리.
도시의 치킨 거리: 모든 집의 치킨 거리의 합.
우리가 할 일: M개의 치킨집만 남기고 나머지를 폐업시켰을 때, 도시의 치킨 거리의 최솟값을 구하는 것.

제약 조건

2 ≤ N ≤ 50
1 ≤ M ≤ 13
집과 치킨집의 개수는 각각 1 이상 100 이하

정답
👉 도시의 치킨 거리의 최솟값을 출력.

💡 접근 방법

입력 받기
- 도시 크기 N, 남길 치킨집 수 M
- 도시 지도 arr 입력
- 집과 치킨집 좌표를 각각 리스트에 저장
조합 생성
- 치킨집이 M개보다 많을 경우, 어떤 치킨집을 살릴지 선택해야 함.
- 즉, 치킨집 리스트 중에서 M개를 뽑는 모든 조합을 고려.
도시 치킨 거리 계산
- 각 집마다 모든 선택된 치킨집 중 최소 거리를 구함.
- 이를 합산하여 도시 치킨 거리를 계산.
최솟값 갱신
- 모든 조합에 대해 도시 치킨 거리를 구하고, 그 중 최솟값을 결과로 저장.

📝 문제 설계

변수
- house: 집 좌표 리스트
- chicken: 치킨집 좌표 리스트
- selected: 현재 선택된 치킨집 조합
- result: 도시 치킨 거리 최솟값
흐름
1. 입력받아 house, chicken 리스트 채우기
2. 치킨집이 M개 초과일 경우 → pickChickenComb() 호출 (조합으로 뽑기)
3. 치킨집이 M개 이하일 경우 → 그냥 calcChickenDist() 실행
4. 각 조합마다 calcChickenDist()를 통해 도시 치킨 거리 계산
5. 최솟값을 result로 갱신
6. 결과 출력
사용 알고리즘
- 조합(Combination) → M개의 치킨집을 뽑기 위해 사용
- 브루트포스(Brute Force) → 모든 경우를 탐색해야 하기 때문에 적합
해당 알고리즘을 선택한 근거
- 남길 치킨집의 개수가 최대 13개라서, 조합의 경우의 수가 충분히 계산 가능한 범위임.
- 최대 경우의 수: C(13, 6) = 1716 → 충분히 가능.
- 각 조합에 대해 모든 집을 탐색해야 하지만, 집은 최대 100개 → 계산량이 크지 않음.
- 따라서 브루트포스로 모든 조합을 탐색하는 방식이 가장 직관적이고 확실한 방법.

입력 & 출력 예시

🧑‍💻 코드

package Baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class B_15686_치킨배달 {
	static int N, M, pickChickenCount, n, r, cityChickenDist, result;
	static int[][] arr;
	static List<int[]> house;
	static List<int[]> chicken;
	static List<int[]> selected;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();		
		arr = new int[N][N];
		pickChickenCount = M;
		house = new ArrayList<>();
		chicken = new ArrayList<>();
		selected = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = sc.nextInt();
				
				// 좌표 저장 [ 0 빈칸 / 1 집 / 2 치킨집 ]
				if (arr[i][j] == 1) {
					house.add(new int[]{i,j});
				} else if (arr[i][j] == 2) {
					chicken.add(new int[]{i,j});
				}
			}
		}
		
		//로직 
		//임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
		//치킨 거리는 집과 가장 가까운 치킨집 사이의 거리
		//즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 
		//도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
		
		//살릴 치킨 집 개수가 지금 지도 상에 있는 치킨 집 개수보다 많을 때 
		//일단 어떤 치킨 집을 살릴지 골라야돼서 
		//조합으로 치킨 집 뽑아서 저장 하려고 
		//치킨 집 뽑는 함수 => pickChickenComb()
		if (chicken.size() > M) {
			int n = chicken.size();
			int r = M;
			result = Integer.MAX_VALUE;
			pickChickenComb(0, 0); 
		} else {
			result = calcChickenDist(chicken);
		}
		
		//출력 
		System.out.println(result);
	}
	
	// 조합 뽑기
	static void pickChickenComb(int start, int depth) {
	    if (depth == M) { 	    	
	        // M개 선택 완료 → 도시 치킨 거리 계산	        
	        result = Math.min(calcChickenDist(selected), result);
	        return;
	    }

	    for (int i = start; i < chicken.size(); i++) {
	        selected.add(chicken.get(i));       // i번째 치킨집 선택
	        pickChickenComb(i + 1, depth + 1);  // 다음 조합 뽑기
	        selected.remove(selected.size() - 1);  // 백트래킹
	    }
	}
	
	//도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
	static int calcChickenDist(List<int[]> targetChickenList) {
		cityChickenDist = 0;
		for (int[] target : house) {
			int chickenDist = Integer.MAX_VALUE;
			for (int[] chicken : targetChickenList) {
				int r1 = target[0];
	            int c1 = target[1];
	            int r2 = chicken[0];
	            int c2 = chicken[1];
	            chickenDist = Math.min(chickenDist, Math.abs(r1 - r2) + Math.abs(c1 - c2)); // 한 집의 치킨 거리
			}			
			cityChickenDist += chickenDist;
		}
		
		return cityChickenDist;
	}

}

🔍코드해설

1️⃣ pickChickenComb(start, depth) — 치킨집 조합 뽑기

static void pickChickenComb(int start, int depth) {
    if (depth == M) {
        result = Math.min(calcChickenDist(selected), result);
        return;
    }
    for (int i = start; i < chicken.size(); i++) {
        selected.add(chicken.get(i));
        pickChickenComb(i + 1, depth + 1);
        selected.remove(selected.size() - 1); // 백트래킹
    }
}

목적

치킨집 리스트(chicken)에서 M개를 선택하는 모든 조합을 생성하고,
각 조합에 대해 calcChickenDist(selected) 를 호출해 도시 치킨 거리 합을 구한 뒤 result(최솟값)를 갱신

파라미터 설명

start : 다음 선택 가능한 치킨집의 시작 인덱스. 중복 조합을 막고 오름차순으로 선택하도록 보장한다.
depth : 현재까지 선택한 치킨집의 개수 (selected.size()와 동일한 값).

동작 흐름(한 단계씩)

기저조건(Base case)
if (depth == M)

이미 M개를 선택했으므로 현재 selected 조합으로 calcChickenDist를 호출해 도시 치킨 거리를 계산하고 result와 비교하여 최소값을 저장.
이후 재귀에서 돌아간다.

재귀 + 반복
for (int i = start; i < chicken.size(); i++)

start부터 끝까지 각 치킨집을 순회하며 하나씩 선택
선택 시 selected.add(chicken.get(i)) 로 추가 후,
pickChickenComb(i + 1, depth + 1) 를 호출하여 다음 위치부터 더 선택
재귀 호출이 끝나면 selected.remove(selected.size() - 1) 로 방금 선택한 항목을 제거(backtracking) 하여 다음 후보 시도

2️⃣ calcChickenDist(targetChickenList) — 치킨 거리 계산

static int calcChickenDist(List<int[]> targetChickenList) {
    int cityChickenDist = 0;
    for (int[] target : house) {
        int chickenDist = Integer.MAX_VALUE;
        for (int[] chicken : targetChickenList) {
            int r1 = target[0], c1 = target[1];
            int r2 = chicken[0], c2 = chicken[1];
            chickenDist = Math.min(chickenDist, Math.abs(r1 - r2) + Math.abs(c1 - c2));
        }
        cityChickenDist += chickenDist;
    }
    return cityChickenDist;
}

목적

주어진 targetChickenList (선택된 치킨집들)에 대해 각 집이 갖는 최소 치킨 거리를 모두 더해 도시의 치킨 거리를 반환

변수 설명

cityChickenDist : 모든 집들의 치킨 거리 합 (최종 반환값)
target : house 리스트에서 현재 처리 중인 집의 좌표 (int[] {r, c})
chickenDist : 해당 집이 갖는 가장 가까운 치킨집과의 거리. 초기값을 Integer.MAX_VALUE 로 둬서 비교로 최소값을 갱신
chicken : targetChickenList의 각 치킨집 좌표

동작 흐름

모든 집(house)에 대해 반복
각 집마다 chickenDist = Integer.MAX_VALUE 로 초기화
선택된 치킨집 리스트를 전부 돌면서 맨해튼 거리 계산:
- Math.abs(r1 - r2) + Math.abs(c1 - c2) (맨해튼 거리)
- chickenDist = Math.min(chickenDist, computedDistance) 로 최소값 유지
한 집의 최소 거리인 chickenDist 를 cityChickenDist에 누적
모든 집을 처리한 후 cityChickenDist 반환