[BOJ] 15686 - 치킨 배달 (Java)

알고리즘

• 구현
• 브루트포스 알고리즘
• 백트래킹

1. 문제

2. Idea

• DFS와 백트래킹 알고리즘을 활용

1. 집과 치킨집의 좌표를 각각 list에 저장
2. 치킨집이 open한 개수가 M과 같다면, 모든 집에 대하여 M개의 치킨집 중 최단거리를 계산
3. 탐색을 시작하는 지점이 치킨집 list의 사이즈가 벗어나게 되면 탐색을 종료

• 백트래킹(backtracking)을 이용하여 조합(combination)을 생성
• 이 과정은 조합을 구성하는 각 원소의 선택 여부를 표시하고, 재귀적으로 조합을 만들어냄
• 선택한 치킨집의 인덱스를 기준으로 다음 치킨집을 선택하는 과정을 반복
• 모든 치킨집을 선택한 후에는 다음 단계로 넘어가기 위해 현재 치킨집을 선택하지 않은 상태로 설정

3. 전체코드

package alss3;

import java.io.*;
import java.util.*;
class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Week10_3{
    static int N, M;
    static int[][] map;
    static ArrayList<Point> person;
    static ArrayList<Point> chicken;
    static int ans;
    static boolean[] open;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        person = new ArrayList<>();
        chicken = new ArrayList<>();

        // 미리 집과 치킨집에 해당하는 좌표를 ArrayList에 넣어 둠.
        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) { 
                // 만약 현재 위치에 집(값이 1)이 있다면, 집의 좌표를 person 리스트에 추가
                    person.add(new Point(i, j));
                } else if (map[i][j] == 2) { // 만약 현재 위치에 치킨집(값이 2)이 있다면, 치킨집의 좌표를 chicken 리스트에 추가
                    chicken.add(new Point(i, j));
                }
            }
        }

        ans = Integer.MAX_VALUE;
        open = new boolean[chicken.size()];

        DFS(0, 0);
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void DFS(int start, int cnt) {
        if (cnt == M) {
            int res = 0;

            for (int i = 0; i < person.size(); i++) {
                int temp = Integer.MAX_VALUE;

                // 어떤 집과 치킨집 중 open한 치킨집의 모든 거리를 비교한다.
                // 그 중, 최소 거리를 구한다.
                for (int j = 0; j < chicken.size(); j++) {
                    if (open[j]) {
                        int distance = Math.abs(person.get(i).x - chicken.get(j).x)
                                + Math.abs(person.get(i).y - chicken.get(j).y);

                        temp = Math.min(temp, distance);
                    }
                }
                res += temp;
            }
            ans = Math.min(ans, res);
            return;
        }

        // 백트래킹을 통해 DFS 수행
        // 모든 치킨집을 선택한 후에는 다음 단계로 넘어가기 위해 현재 치킨집을 선택하지 않은 상태로 설정
        for (int i = start; i < chicken.size(); i++) {
            open[i] = true;
            DFS(i + 1, cnt + 1);
            open[i] = false;
        }
    }
}