피자 배달 거리(DFS, 삼성 SW역량평가 기출)

문제설명

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다. 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다.
예를 들어, 도시의 지도가 아래와 같다면

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다. 도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다. 도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

입력 설명

• 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.
• 둘째 줄부터 도시 정보가 입력된다.
  
  

출력 설명

• 첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.
  

입력예제

4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2

출력예제

6

내 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main_8_14 {
    static int n, m;
    static int len, answer = Integer.MAX_VALUE;
    static int[] combi;
    static ArrayList<Points> house, pizza;

    public void dfs(int l, int s){
        if(l == m){
            int sum = 0;
            for(Points h : house){
                int dis = Integer.MAX_VALUE;
                for(int i : combi){
                    dis = Math.min(dis, Math.abs(h.x - pizza.get(i).x) + Math.abs(h.y - pizza.get(i).y));
                }
                sum += dis;
            }
            answer = Math.min(answer, sum);
        }
        else{
            for(int i = s; i < len; i++){
                combi[l] = i;
                dfs(l+1, i+1);
            }
        }
    }

    public static void main(String[] args) {
        Main_8_14 t = new Main_8_14();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        house = new ArrayList<>();
        pizza = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                int tmp = kb.nextInt();
                if(tmp == 1)
                    house.add(new Points(i,j));
                else if(tmp == 2)
                    pizza.add(new Points(i,j));
            }
        }
        len = pizza.size();
        combi = new int[m];
        t.dfs(0,0);
        System.out.println(answer);
    }
}

• DFS를 활용하여 풀어보았다.
• 문제에서 요구하는 답은 각 집마다의 피자배달거리가 아닌 도시의 피자배달거리이다.
• 도시의 피자배달거리(sum) = 각 집의 피자배달거리의 합
• 6개의 피자집 중 4개의 피자집을 고르는 것이니 6C4로 15가지의 피자집 조합이 나온다.(위 코드에서 dfs 함수를 통해 조합을 구하였다. ex: 0 1 2 3, 0 1 2 4, 0 1 2 5...)
• 조합은 combi배열에 저장되며 저장된 값은 pizzaArrayList에 index를 의미한다.
• houseArrayList에 있는 집의 좌표와 인덱스를 가르키는 조합의 값을 토대로 pizzaArrayList의 좌표와 거리를 구한 후 sum에 누적시켜 더해준다.
• 이 과정을 반복하여 sum 중에 가장 작은 값이 도시의 최소 피자배달거리이다.