[JAVA]백준 치킨배달

 

www.acmicpc.net/problem/15686

 

위의 문제풀이에 대하여 알아보겠다.

1. 좌표값에 대하여 치킨집, 집에 대한 ArrayList를 각각 생성한다.

 

2. 위의 생성한 ArrayList에 Input받는 동시에 각각의 Dot(x,y)객체를 집어넣는다.

 

3. 백트래킹을 이용할것이다.

=>Combination(DFS)을 이용하여, 각각의 집에 대하여 치킨집까지 거리를 계산해서

그중에서 최소값을 택하여 min값에 넣어준다.

해당 min값은 sum에 추가한다.

 

 

ex) Calc부분과 min값 구하는 방법 설명

output	currentM = Calc(person.get(i), chicken.get(output[j] - 1));
0,1	Calc(각 사람, 치킨집(0번째&1번째 선택))
0,2	Calc(각 사람, 치킨집(0번째&2번째 선택))
0,3	Calc(각 사람, 치킨집(0번째&3번째 선택))
1,2	Calc(각 사람, 치킨집(1번째&2번째 선택))
1,3	Calc(각 사람, 치킨집(1번째&3번째 선택))
2,3	Calc(각 사람, 치킨집(2번째&3번째 선택))

첫번째 경우를 살펴보자.

min값에는 특정 집A에 대하여 0번째치킨집과 1번째 치킨집 중 가까운 거리를 대입해주면된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Main {
    static int N;
    static int M;
    static int[][] arr;
    static ArrayList<Dot> chicken;
    static ArrayList<Dot> person;
    static int[] output;
    static boolean[] visited;
    static int result;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        arr = new int[N][N];
        result = Integer.MAX_VALUE;
        chicken = new ArrayList<Dot>();
        person = new ArrayList<Dot>();

        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
                if (arr[i][j] == 1) {
                    //1일때는 사람 list에 추가
                    person.add(new Dot(i, j));
                } else if (arr[i][j] == 2) {
                    //2일때는 치킨 list에 추가
                    chicken.add(new Dot(i, j));
                }
            }
        }
        //-------입력부-------//

        //치킨 집 선택을 위한 배열 visited, output
        visited = new boolean[chicken.size()];
        output = new int[chicken.size()];//combination 고르는것.

        //치킨 집 선택
        for (int i = 0; i < chicken.size(); i++) {
            visited[i] = true;
            ChickenSelection(i, 0);
            visited[i] = false;
        }
        System.out.println(result);
    }

    //치킨집 선택을 위한 함수
    public static void ChickenSelection(int start, int depth) {
        output[depth] = start + 1;

        for (int i = start; i < chicken.size(); i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            ChickenSelection(i, depth + 1);
            visited[i] = false;
        }
        //치킨집이 선택되었을 경우
        //(치킨집이 최대 M개 이므로 depth은 M-1 이 되어야한다. 0부터 시작했으니깐)
        if (depth == M - 1) {
            int sum = 0;
            int currentM = 0;
            //사람이 갈수 있는 치킨집의 경우중 가장 최소값을 선택한다.
            //person 한명씩 모든 Chicken 집을 선택하여 최소값을 비교한다.
            for (int i = 0; i < person.size(); i++) {//각 사람에 대하여 치킨집까지 거리 구하기
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < M; j++) {
                    currentM = Calc(person.get(i), chicken.get(output[j] - 1));
                    min = Math.min(min, currentM);
                }
                //최소값일 경우 더한다.
                sum = sum + min;
            }
            //치킨집 경우의 수마다 다른 최소거리중 가장 작은 최소거리를 선택한다.
            result = Math.min(result, sum);
        }
    }

    //위치 거리 계산 함수
    public static int Calc(Dot d1, Dot d2) {
        return Math.abs(d1.x - d2.x) + Math.abs(d1.y - d2.y);
    }
}

class Dot {
    int x;
    int y;

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