[백준, 15686번] 치킨 배달 (브루트 포스, 백트래킹, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 치킨 배달" 문제는 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

전체 코드

 

코드의 주요 로직은 다음과 같습니다:

1. 전역 변수 설정
   • HOUSE(1), CHICKEN(2): 도시의 각 칸의 상태를 나타내는 상수
   • chickenHouses, houses: 치킨집과 집의 좌표를 저장할 ArrayList
   • N, M: 도시의 크기와 남겨야 할 치킨집의 수
   • result: 도시의 최소 치킨 거리를 저장할 변수
2. 입력 및 초기화
   • N×N 크기의 도시 정보를 입력받으면서 치킨집과 집의 좌표를 각각의 ArrayList에 저장
   • 좌표는 int[] 배열 형태로 {행, 열} 저장
3. 치킨 거리 계산 (calMinChickenDistance)
   • 치킨집의 수가 M보다 크면
     • 조합을 통해 M개의 치킨집 선택
   • 치킨집의 수가 M 이하면
     • 현재 있는 모든 치킨집으로 거리 계산
   • 각 집에서 가장 가까운 치킨집까지의 거리 계산 (|r1-r2| + |c1-c2|)
4. 조합 구현 (combi)
   • 백트래킹을 사용하여 M개의 치킨집을 선택하는 모든 조합 생성
   • visited 배열로 현재 선택된 치킨집 관리
   • 각 조합에 대해:
     • 모든 집에서 선택된 치킨집까지의 최소 거리 계산
     • 모든 집의 치킨 거리 합을 구하고 최솟값 갱신
5. 최종 결과
   • 모든 조합을 확인한 후, 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());

    }
}