링크

치킨 배달

문제

풀이

백트래킹을 사용해서 완전탐색을 했다.
치킨집의 경우의 수를 모두 탐색해 거리를 계산하여 최솟값을 찾았다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Node{
    int x;
    int y;

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

    @Override
    public String toString() {
        return "Node{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}

//15686
public class Main {
    public static int[][] matrix = null;
    public static boolean[] visited;
    public static int answer = Integer.MAX_VALUE;
    public static List<Node> chicken = new ArrayList<>();
    public static List<Node> house = new ArrayList<>();
    public static List<Node> liveChicken = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        matrix = new int[n][n];

        for(int i=0;i<n;i++){
            arr = br.readLine().split(" ");

            for(int j=0;j<arr.length;j++){
                matrix[i][j] = Integer.parseInt(arr[j]);

                if(matrix[i][j] == 1){
                    house.add(new Node(i, j));
                } else if(matrix[i][j] == 2){
                    chicken.add(new Node(i, j));
                }
            }
        }
        visited = new boolean[chicken.size()];

//        System.out.println(chicken);
//        System.out.println("-----------------");

        //백트래킹
        dfs(0, 0, m);
        System.out.println(answer);
    }

    public static void dfs(int dept, int last, int limit){
        if(dept == limit){
//            System.out.println(liveChicken);
            int result = distance();
            answer = Math.min(answer, result);

            return;
        }

        for(int i=0;i<visited.length;i++){
            if(!visited[i] && i >= last){
                visited[i] = true;
                dept+=1;
                liveChicken.add(chicken.get(i));
                dfs(dept, i, limit);
                dept-=1;
                liveChicken.remove(liveChicken.size() - 1);
                visited[i] = false;
            }
        }


    }

    //치킨거리 계산 = |x1 - x2| + |y1 - y2|
    public static int distance(){
        //house에 대해 각각의 치킨집 거리랑 비교해서 적은곳을 선정
        int totalDis = 0;

        for(int i=0;i<house.size();i++){
            int houseX = house.get(i).x;
            int houseY = house.get(i).y;

            int minDis = Integer.MAX_VALUE;
            for(int j=0;j<liveChicken.size();j++){
                int chickenX = liveChicken.get(j).x;
                int chickenY = liveChicken.get(j).y;

                minDis = Math.min(minDis, (Math.abs(houseX - chickenX) + Math.abs(houseY - chickenY)));
            }

            totalDis += minDis;
        }

        return totalDis;

    }

}