[BOJ] 백준 [15686] 치킨배달 JAVA

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

[문제]

[풀이]

치킨 집 - 가정 집 사이의 거리를 최소로 하는 치킨 집들을 구해서 거리 합을 구하는 문제이다.

주어진 map 상태를 보면 중간에 벽이 없이 거리는 (x2-x1)+(y2-y1) 으로 구하면 되기 때문에
그래프를 탐색 하지 않고 모든 치킨 집과 가정 집 사이의 거리를 다 구해서
최소를 찾는 완전탐색을 하면 된다.

탐색의 크기는 치킨 집 좌표의 갯수를 기준으로 visit 방문 배열의 크기로 정해준다.

import java.util.stream.*;
import static java.util.Arrays.*;
import static java.util.stream.Collectors.*;

import java.util.*;
import java.io.*;

public class Main {

    static boolean[] visit;
    static ArrayList<int[]> house,chicken;
    static int[][] map;
    static int n,m,minSum=Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        n = input[0]; m = input[1];
        map = new int[n][n];
        house = new ArrayList<>();
        chicken = new ArrayList<>();

        for(int i=0;i<n;i++){
            map[i] = stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
            for(int j=0;j<n;j++){
                if(map[i][j]==1) house.add(new int[]{j,i});
                else if(map[i][j]==2) chicken.add(new int[]{j,i});
            }
        }//end input
        visit = new boolean[chicken.size()];// 치킨 집 갯수만큼 크기 지정
        dfs(0,0,new ArrayList<Integer>());
        System.out.println(minSum);
    }

    static void dfs(int cur, int depth, ArrayList<Integer> indexList) {

        if(depth==m){

            int distanceSum=0;
            for (int[] housePos : house) {

                int minDistance=Integer.MAX_VALUE;
                for (Integer index : indexList) {
                    int[] chickenPos = chicken.get(index);
                    minDistance = Math.min(Math.abs(chickenPos[1] - housePos[1])+
                            Math.abs(chickenPos[0] - housePos[0]),minDistance);
                }
                distanceSum+=minDistance;
            }
            minSum = Math.min(distanceSum,minSum);
            return;
        }

        for(int next=cur;next<chicken.size();next++){

            if(!visit[next]){
                visit[next]=true;
                indexList.add(next); // 치킨 집 인덱스 추가
                dfs(next,depth+1,indexList);
                visit[next]=false;
                indexList.remove((Integer)next); // object 형태로 형 변환해서 제거
            }
        }
    }
}