문제설명

입력 & 출력

나의 풀이
문제 접근 방법
"백준 - 치킨 배달" 문제는 NxN 크기의 도시를 배경으로, 다음 조건을 만족하며 도시의 최소 치킨 거리를 구하는 문제입니다.
- 도시의 각 칸은 비어 있는 곳(0), 집(1), 치킨집(2) 중 하나로 구성됩니다.
- 치킨 거리는 한 집과 가장 가까운 치킨집 사이의 거리를 의미합니다.
- 도시의 치킨 거리는 모든 집의 치킨 거리의 합입니다.
- 도시에는 여러 치킨집이 있지만, 최대 M개의 치킨집만 유지하고 나머지는 폐업해야 합니다.
이 조건에서, 도시의 치킨 거리가 최소가 되도록 치킨집을 선택하는 방법을 구하는 것이 목표입니다.
두 가지의 예제를 가지고 접근 방법을 살펴보겠습니다.
예제 입력 1
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2
위와 같이 입력이 주어졌을 때 치킨 도시를 구하면 다음과 같습니다.

M은 3이고, 치킨집 또한 3개입니다. 따라서 이 경우에는 폐업을 할 필요가 없기 때문에 각 집에서 가장 가까운 치킨집과의 거리를 구하면 되는 경우입니다.
치킨집과의 거리는 |r1-r2| + |c1-c2| 로 구하면 되고, 각 집에서 가까운 치킨집과의 거리를 구하면 다음과 같습니다.

- 집 (1,3)
- 거리 to (2,3): ∣1−2∣+∣3−3∣=1
- 거리 to (3,3): ∣1−3∣+∣3−3∣=2
- 거리 to (5,5): ∣1−5∣+∣3−5∣=6
- 최소 거리 = 1
- 집 (2,5):
- 거리 to (2,3): ∣2−2∣+∣5−3∣=2
- 거리 to (3,3): ∣2−3∣+∣5−3∣=3
- 거리 to (5,5): ∣2−5∣+∣5−5∣=3
- 최소 거리 = 2
- 집 (3,2):
- 거리 to (2,3): ∣3−2∣+∣2−3∣=2
- 거리 to (3,3): ∣3−3∣+∣2−3∣=1
- 거리 to (5,5): ∣3−5∣+∣2−5∣=5
- 최소 거리 = 1
- 집 (4,3):
- 거리 to (2,3): ∣4−2∣+∣3−3∣=2
- 거리 to (3,3): ∣4−3∣+∣3−3∣=1
- 거리 to (5,5): ∣4−5∣+∣3−5∣=3
- 최소 거리 = 1
이 예제 입력에서는 폐업을 할 필요가 없기 때문에 각 집에서 최솟값을 가지는 거리를 다 더하면 우리가 구해야할 도시의 치킨 거리의 최솟값(1 + 2 + 1 + 1 = 5)이 됩니다.
예제 입력 2
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
위 경우는 M은 2이고, 치킨집은 5개입니다. 이 경우에는 도시의 치킨거리가 최솟값을 가지도록 3개의 치킨집을 폐업해야합니다.

입력을 기반으로 도시를 만들면 위와 같이 형성이 되고, 5개의 치킨집 중에서 2개를 선택하는 조합을 구하는 것이므로 5C2 = 10가지의 조합이 나오게 됩니다.


- 1. (1,2), (4,1) 선택
- (1,4) 집까지: min(|1-1|+|4-2|, |1-4|+|4-1|) = min(2, 6) = 2
- (2,1) 집까지: min(|2-1|+|1-2|, |2-4|+|1-1|) = min(2, 3) = 2
- (2,3) 집까지: min(|2-1|+|3-2|, |2-4|+|3-1|) = min(2, 4) = 2
- (4,4) 집까지: min(|4-1|+|4-2|, |4-4|+|4-1|) = min(5, 3) = 3
- (4,5) 집까지: min(|4-1|+|5-2|, |4-4|+|5-1|) = min(6, 4) = 4
- (5,4) 집까지: min(|5-1|+|4-2|, |5-4|+|4-1|) = min(6, 4) = 4
- 각 집의 최소 치킨 거리 합: 17
- (1,2), (5,5) 선택
- (1,4) 집까지: min(|1-1|+|4-2|, |1-5|+|4-5|) = min(2, 5) = 2
- (2,1) 집까지: min(|2-1|+|1-2|, |2-5|+|1-5|) = min(2, 7) = 2
- (2,3) 집까지: min(|2-1|+|3-2|, |2-5|+|3-5|) = min(2, 5) = 2
- (4,4) 집까지: min(|4-1|+|4-2|, |4-5|+|4-5|) = min(5, 2) = 2
- (4,5) 집까지: min(|4-1|+|5-2|, |4-5|+|5-5|) = min(6, 1) = 1
- (5,4) 집까지: min(|5-1|+|4-2|, |5-5|+|4-5|) = min(6, 1) = 1
- 각 집의 최소 치킨 거리 합: 10
전체 코드


코드의 주요 로직은 다음과 같습니다:
- 전역 변수 설정
- HOUSE(1), CHICKEN(2): 도시의 각 칸의 상태를 나타내는 상수
- chickenHouses, houses: 치킨집과 집의 좌표를 저장할 ArrayList
- N, M: 도시의 크기와 남겨야 할 치킨집의 수
- result: 도시의 최소 치킨 거리를 저장할 변수
- 입력 및 초기화
- N×N 크기의 도시 정보를 입력받으면서 치킨집과 집의 좌표를 각각의 ArrayList에 저장
- 좌표는 int[] 배열 형태로 {행, 열} 저장
- 치킨 거리 계산 (calMinChickenDistance)
- 치킨집의 수가 M보다 크면
- 조합을 통해 M개의 치킨집 선택
- 치킨집의 수가 M 이하면
- 현재 있는 모든 치킨집으로 거리 계산
- 각 집에서 가장 가까운 치킨집까지의 거리 계산 (|r1-r2| + |c1-c2|)
- 치킨집의 수가 M보다 크면
- 조합 구현 (combi)
- 백트래킹을 사용하여 M개의 치킨집을 선택하는 모든 조합 생성
- visited 배열로 현재 선택된 치킨집 관리
- 각 조합에 대해:
- 모든 집에서 선택된 치킨집까지의 최소 거리 계산
- 모든 집의 치킨 거리 합을 구하고 최솟값 갱신
- 최종 결과
- 모든 조합을 확인한 후, result에 저장된 최소 치킨 거리 반환
이렇게 구현하여 M개의 치킨집을 선택했을 때 도시의 치킨 거리가 최소가 되는 값을 찾습니다.
만약 조합이 없으면 다음과 같이만 최솟값을 가지는 도시 치킨 거리만 구하면 됩니다.
package Gold5;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
// 치킨 배달
// 도시의 치킨 거리 : 모든 집의 치킨 거리의 합
// 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력
// |r1-r2| + |c1-c2|
public class BOJ15686 {
static final int HOUSE = 1;
static final int CHICKEN = 2;
static List<int[]> chickenHouses;
static List<int[]> houses;
public static int calMinChickenDistance(){
int totalDistance = 0;
for (int[] house : houses){
int min = Integer.MAX_VALUE;
for (int[] chicken : chickenHouses){
int distance = Math.abs(house[0] - chicken[0]) + Math.abs(house[1] - chicken[1]);
min = Math.min(min, distance);
}
totalDistance += min;
}
return totalDistance;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer token = new StringTokenizer(br.readLine());
int N = Integer.parseInt(token.nextToken()); // 도시 크기 N x N
int M = Integer.parseInt(token.nextToken()); // 폐업시키지 않을 치킨집의 개수
houses = new ArrayList<>(); // 집 좌표 저장 리스트
chickenHouses = new ArrayList<>(); // 치킨집 좌표 저장 리스트
int[][] city = new int[N+1][N+1];
for (int i = 1; i <= N ; i++) {
token = new StringTokenizer(br.readLine());
for (int j = 1; j <= N ; j++) {
city[i][j] = Integer.parseInt(token.nextToken());
if(city[i][j] == HOUSE){
houses.add(new int[]{i,j});
} else if (city[i][j] == CHICKEN) {
chickenHouses.add(new int[]{i,j});
}
}
}
System.out.println(calMinChickenDistance());
}
}'Coding Test > 백준' 카테고리의 다른 글
| [백준, 2468번] 안전 영역 (DFS, 깊이 우선 탐색, Java) (0) | 2025.01.24 |
|---|---|
| [백준, 11725번] 트리의 부모 찾기 (DFS, 트리, Java) (0) | 2025.01.23 |
| [백준, 9251번] LCS (LCS, 최장 공통 부분 수열, Java) (1) | 2025.01.19 |
| [백준, 14889번] 스타트와 링크 (백트래킹, 브루트 포스, Java) (0) | 2025.01.13 |
| [백준, 12865번] 평범한 배낭 (다이나믹 프로그래밍 : DP, 배낭 문제 : Knapsack, Java) (0) | 2025.01.11 |