[백준/JAVA] 15686번: 치킨 배달

🔺 문제

15686번: 치킨 배달

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[][] map;
 
    static List<int[]> chickens = new ArrayList<>();    // 치킨집 위치 저장 리스트
    static List<int[]> houses = new ArrayList<>();      // 집 위치 저장 리스트
 
    static boolean[] selected;
    static int min = Integer.MAX_VALUE;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        map = new int[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                if (map[i][j] == 1) {
                    houses.add(new int[]{i, j});
                } else if (map[i][j] == 2) {
                    chickens.add(new int[]{i, j});
                }
            }
        }
 
        selected = new boolean[chickens.size()];
        combination(0, 0);
        System.out.println(min);
    }
 
    // 백트래킹 + 조합 메소드
    private static void combination(int start, int cnt) {
        if (cnt == M) { // 치킨 거리 최솟값 구하기
            min = Math.min(min, calculateDistance());
            return;
        }
 
        // 백트래킹
        for (int i = start; i < chickens.size(); i++) {
            if(!selected[i]) {
                selected[i] = true;
                combination(i + 1, cnt + 1);
                selected[i] = false;
            }
        }
    }
 
    // 치킨 거리 계산 메소드
    private static int calculateDistance() {
        int total = 0;  // 도시의 치킨 거리
 
        for (int[] house : houses) {
            int tmp = Integer.MAX_VALUE;
            
            // 어떤 집과 치킨 집 중 선택된 치킨집의 모든 거리 비교하고, 이 중 최소 거리 계산
            for (int i = 0; i < chickens.size(); i++) {
                if(selected[i]) {
                    int[] chicken = chickens.get(i);
                    int distance = Math.abs(house[0] - chicken[0]) + Math.abs(house[1] - chicken[1]);
                    
                    tmp = Math.min(tmp, distance);
                }
            }
            total += tmp;
        }
 
        return total;
    }
}
 

✅ 해결 아이디어
✔ 백트래킹 + 조합
- 집과 치킨집 위치를 각자 ArrayList에 따로 저장

- M개의 뽑은 치킨집은 boolean 타입으로 선언해 이미 뽑았는지 여부와 함께 각 도시의 치킨 거리 구할 때 사용

- 좌표값 사용해 모든 치킨집까지의 거리 계산한 후 그 중 최소값 탐색 (브루트포스)

 

 

💥 유의사항

• BFS와 재귀함수를 이용하면 시간 초과가 뜬다고 함 (참고)

 

 

---

🔺 다른 풀이들

- 다들 비슷하심. 나는 ArrayList를 int[] 로 만들었는데 Point 클래스 사용하신 분들도 있음

 

---

💬 느낀 점

백트래킹과 조합 문제를 많이 풀어봐야겠다...

2차원 배열과 "최솟값" 구하는 문제래서 그냥 bfs 활용하면 될 줄 알았는데 그게 아니었다..

머리야 잘 돌아가자...

 

 

1회독	2회독	3회독	4회독	5회독
V	240521

---

(참고)

[백준]15686: 치킨 배달 - JAVA

[BOJ] 백준 15686번 : 치킨 배달 (JAVA)

[백준] 15686번 치킨 배달 - Java, 자바