섹션 8 DFS, BFS - 14. 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)

문제 설명

N×N 크기의 도시 지도에는 다음과 같은 정보가 주어진다:

• 0: 빈칸
• 1: 집
• 2: 피자집

도시의 각 집은 여러 피자집 중 가장 가까운 피자집을 선택해 피자 배달을 받는다.
피자 배달 거리는 |x1 - x2| + |y1 - y2| 로 계산한다.

도시의 전체 피자 배달 거리는 각 집의 배달 거리의 총합이다.

도시에는 피자집이 여러 개 있지만, M개만 남기고 나머지는 폐업하려 한다.
M개의 피자집을 골랐을 때, 도시의 피자 배달 거리의 최소값을 구하라.

---

입력 & 출력

입력

• 첫째 줄: N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)
• 다음 N줄: 도시 정보 (0, 1, 2로 구성된 N×N 정수)

출력

• 도시의 최소 피자 배달 거리

예시 입력

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

 

예시 출력

6

---

해결 방법

• 피자집들 중 M개를 선택하는 조합을 구하고,
• 선택된 조합에 대해 모든 집에서 가장 가까운 피자집을 찾아 거리 합을 구함
• 이 중 가장 최소가 되는 값을 answer로 갱신

---

코드 구현

import java.util.*;

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

    static int n, m, len, answer = Integer.MAX_VALUE;
    static int[] combi;
    static ArrayList<Point> pz, hs;

    public void DFS(int L, int s) {
        if (L == m) {
            int sum = 0;
            for (Point h : hs) {
                int dis = Integer.MAX_VALUE;
                for (int i : combi) {
                    dis = Math.min(dis,
                        Math.abs(h.x - pz.get(i).x) + Math.abs(h.y - pz.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 T = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        pz = new ArrayList<>();
        hs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int tmp = sc.nextInt();
                if (tmp == 1) hs.add(new Point(i, j));
                else if (tmp == 2) pz.add(new Point(i, j));
            }
        }
        len = pz.size();
        combi = new int[m];
        T.DFS(0, 0);
        System.out.println(answer);
        sc.close();
    }
}

---

코드 설명

• Point: (x, y) 좌표 저장 클래스
• hs, pz: 각각 집과 피자집 좌표 리스트
• combi: 선택된 M개의 피자집 인덱스 조합 저장
• DFS: 피자집 M개를 조합으로 선택
  • 선택된 조합에 대해 모든 집과의 거리 최소값을 더함
  • 도시의 피자 배달 거리 중 최소값을 answer로 갱신
• main:
  • 입력받아 집과 피자집 분류
  • DFS 실행 후 최소 피자 배달 거리 출력

---

시간 복잡도 분석

• 피자집 개수: 최대 13개 (문제 조건상)
• M개 선택 조합 수: 최대 C(13, M) = ~700개 이내
• 각 조합마다, 모든 집(최대 100개)과 M개의 피자집 거리 계산 → O(H × M)
• 전체 시간 복잡도: O(조합 수 × 집 수 × M) → 최대 수천 번 연산 → 충분히 빠름

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런