[백준] 15686 치킨 배달 java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static int[][] map;
    static ArrayList<Point> chickenMap;
    static ArrayList<Point> houseMap;
    static Stack<Point> selectedChicken;
    static int minDist;

    public static void dfs(int start, int cnt) {
        if(cnt == M) {
            calculate();
            return;
        }

        for(int i = start; i < chickenMap.size(); i++) {
            selectedChicken.push(chickenMap.get(i));
            dfs(i+1, cnt+1);
            selectedChicken.pop();
        }
    }

    public static void calculate() {
        int sum = 0;
        for(Point house : houseMap) {
            int min = Integer.MAX_VALUE;
            for (Point chicken : selectedChicken) {
                int dist = (Math.abs(house.x - chicken.x)) + (Math.abs(house.y - chicken.y));
                min = Math.min(min, dist);
            }
            sum += min;
            //한 집으로부터 최소 치킨 거리가 현재까지 구한 최소 치킨 거리보다 클 경우 유망하지 않기 때문에 가지치기(백트래킹)
            if(sum > minDist) {
                return;
            }
        }
        minDist = Math.min(sum, minDist);
    }

    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+1][N+1];
        chickenMap = new ArrayList<>();
        houseMap = new ArrayList<>();
        selectedChicken = new Stack<>();
        minDist = Integer.MAX_VALUE;

        //집과 치킨집의 개수를 구한다.
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2) {
                    chickenMap.add(new Point(i, j));
                }
                //집의 좌표값을 미리 저장
                if(map[i][j] == 1) {
                    houseMap.add(new Point(i, j));
                }
            }
        }

        dfs(0, 0);
        System.out.println(minDist);
    }
}

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

완전탐색 문제로 순열 알고리즘을 이용해서 풀이했다.

 

1. ArrayList를 이용해서 각 집의 좌표값과 각 치킨집의 좌표값을 구한다.

2. n개의 치킨집 중에서 m개 만큼의 치킨집의 모든 조합의 최소 치킨 거리를 구한다. (dfs + stack 사용)

3. 시간초과를 피하기 위해서 최소 치킨 거리를 구하는 도중에 현재 최소 치킨 거리보다 크다면 백트래킹을 사용한다.

4. 최소 치킨 거리를 출력한다.