알고리즘) 피자 배달 거리(삼성 SW역량평가 기출문제, DFS)

문제 ✨

 N x N 크기의 지도가 있고, 이는 1 x 1 크기의 격자칸으로 구성되어있다. 각 격자칸에 0은 빈칸, 1은 집, 2는 피자집으로 표현된다. 각 집의 피자배달거리는 해당 집과 도시에 존재하는 피자집들과의 거리 중 최소값을 해당 집의 피자배달거리라고 한다. M개의 피자집만 살리고 나머지는 폐업시킨다고 할 때, 도시의 피자배달거리 최소값을 구하라. (도시의 피자배달거리는 각 집의 피자배달거리를 합친 값이다.)

풀이 ✨

 인접 행렬을 구성하는 값들을 입력받을 때 피자 가게(2)들과 집(1)들을 리스트로 구성하고 피자 가게 리스트의 내부 요소들을 가지고 루프를 돌게 했다. 해당 순서의 피자 가게를 선택하는 경우(checked[idx] = true)와 그렇지 않은 경우(checked[idx] = false) 두 가지 모두 DFS 메서드를 재귀 호출하게 하였다. 이 때, 해당 피자 가게를 선택하는 경우에는 cnt가 증가시키고 cnt가 m이 되는 경우에 최소 배달 거리이 최솟값인지 확인한다.

작성 코드 ✍️

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

public class Main {
    static int n;
    static int m;
    static int[][] matrix;
    static List<Point> list;
    static List<Point> customers;
    static boolean[] checked;
    static int min = Integer.MAX_VALUE;

    static class Point {
        int y;
        int x;

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

    void DFS(int idx, int cnt) {
        if (cnt == m) {
            int total = 0;

            // 해당 피자집에 대한 집들의 거리
            for (int i = 0; i < customers.size(); i++) {
                int dist = Integer.MAX_VALUE; // 각 집의 피자배달거리
                for (int j = 0; j < list.size(); j++) {
                    if (checked[j]) {
                        int y = Math.abs(customers.get(i).y - list.get(j).y);
                        int x = Math.abs(customers.get(i).x - list.get(j).x);
                        dist = Math.min(dist, y + x);
                    }

                }
                total += dist;
            }

            min = Math.min(min, total);
        } else {
            if (idx + 1 < list.size()) {
                checked[idx] = true;
                DFS(idx + 1, cnt + 1);
                checked[idx] = false;
                DFS(idx + 1, cnt);
            }
        }
    }

    public static void main(String args[]) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        matrix = new int[n + 1][n + 1];
        list = new ArrayList<>();
        customers = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                matrix[i][j] = sc.nextInt();
                if (matrix[i][j] == 2) list.add(new Point(i, j));
                else if (matrix[i][j] == 1) customers.add(new Point(i, j));
            }
        }
        checked = new boolean[list.size()];
        main.DFS(0, 0);
        System.out.println(min);
    }

}