피자 배달 거리

피자 배달 거리

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)이 주어진다.

둘째 줄부터 도시 정보가 입력된다.

출력 설명

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.

둘째 줄부터 도시 정보가 입력된다.

입력

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

출력

6

구현 코드

public class 피자배달거리_DFS_삼성SW역량평가 {
    static int n;
    static int m;
    static int[][] board;
    static ArrayList<Point> house;
    static ArrayList<Point> pizza;

    //조합
    static int[] combi;
    static int minPizzaDistanceSum = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();//도시 지도 크기
        m = in.nextInt();//살리고자 하는 피자집 개수
        board = new int[n + 1][n + 1];//1-n까지

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                board[i][j] = in.nextInt();
            }
        }

        house = new ArrayList<>();
        pizza = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (board[i][j] == 2)
                    pizza.add(new Point(i, j));
                if (board[i][j] == 1)
                    house.add(new Point(i, j));
            }
        }

        combi = new int[m];

        dfs(0, 0);
        //피자집 개수 중에 m개 뽑는 조합 구하기
        System.out.println(minPizzaDistanceSum);
    }

    static void dfs(int L, int start) {
        if (L == m) {
            //조합 완성 combi
            int sum = calDeliveryDistance(combi);
            if (minPizzaDistanceSum >= sum) {
                minPizzaDistanceSum = sum;
            }
        } else {
            for (int i = start; i < pizza.size(); i++) {
                combi[L] = i;
                dfs(L + 1, i + 1);
            }
        }
    }

    static int calDeliveryDistance(int[] combi) {
        //combi를 써야함
        int minDistance = Integer.MAX_VALUE;
        int sum = 0;
        for (Point h : house) {
            //각 피자집들에 대해서 배달거리 구하고 최솟값 찾기
            for (int index : combi) {
                Point p = pizza.get(index);
                int dis = Math.abs(p.x - h.x) + Math.abs(p.y - h.y);
                if (minDistance >= dis) {
                    minDistance = dis;
                }
            }
            sum += minDistance;
            minDistance = Integer.MAX_VALUE; //초기화
        }
        return sum;
    }

    static class Point {
        int x;
        int y;

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

문제 보자마자 이차원배열에 거리를 구한다? 이건 전문제들같이 방향 돌면서 하면 되겠네..라고 무식하게 생각하고 알고리즘을 고안했음.
처음에 생각한 알고리즘은 다음과 같음.

for(전체 탐색)
if(board==1)
for(방향 8개 검색)
if(board==2)
배달거리 계산

대충 크게 이런식으로 하면 되지 않을까 생각했는데 이 경우에 m개를 선택해서 조합에 대한 배달거리 계산을 해야하는데 어디에서 할지 코드를 짜다보니 방향이 안잡혀서 고민하다가 강의를 들었음.
코드자체는 참고안하고 arraylist사용하고 조합쓰는 아이디어만 알아내고 다시 짰음.

• 알고리즘

  house arraylist와 pizza arraylist 선언
  for(전체)
        if(house)
          house.add
        if(pizza)
          pizza.add
  pizza집중 m개 조합 구하기 -> 조합 구현 후 combi배열에 넣기
  조합 구해질 때마다 m개의 각 피자집에 대한 집들의 배달 거리 구하고 그 중 최솟값을 sum에 저장 (sum:도시의 최소 배달거리, 즉 모든 집의 최소배달거리의 합)
  조합마다 sum을 내므로 sum중에서 가장 최소 sum 비교 후 출력

문제 풀고나서 느낀점
: 삼성 역량 평가는 나의 범위가 아니겠구나..
열심히 공부해야지.. 오늘도 눈물 한방울