Java : 피자 배달 거리

문제

풀이

1. 조합 + dfs 문제
2. 피자집 m개를 제외하고 폐업하기 때문에 전체 피자집에서 m개를 선택해야한다.
3. 즉 피자집 배열에서 m개를 선택하는 조합을 사용한다.
4. dfs 에서 m개를 뽑으면(level==m) 각 집마다 뽑힌 피자집과의 거리를 계산한다.
5. 최소 배달 거리의 합을 구하고 각각의 경우의 수에서 최소 값을 구한다.

• 처음에는 m이 어떻게 쓰이는지 생각이 안나서 삽질만 하다가 인강을 보고 조합의 사용여부를 확인했다.
• 조합을 쓴다해도 조합 개수 공식만 외우고 있던 터라 조합 배열의 값을 어떻게 구할지도 생각이 안 나서 애를 먹었다.

전체 코드

package inflearn;

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

public class I0814 {
  static int n, m, len, ans = Integer.MAX_VALUE;
  static int[] combi;
  static ArrayList<Point> homeArr;
  static ArrayList<Point> pizzaArr;

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    n = sc.nextInt();
    m = sc.nextInt();
    combi = new int[m];

    homeArr = new ArrayList<>();
    pizzaArr = new ArrayList<>();


    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        int v = sc.nextInt();

        if (v == 1) homeArr.add(new Point(i, j));
        if (v == 2) pizzaArr.add(new Point(i, j));
      }
    }

    len = pizzaArr.size();
    dfs(0, 0);
    System.out.println(ans);
  }

  static void dfs(int level, int start) {
    // 조합에서 m개를 뽑았을 때
    if (level == m) {
      int sum = 0;
      for (Point point : homeArr) {
        int dis = Integer.MAX_VALUE;
        for (int i : combi) {
          dis = Math.min(dis, Math.abs((point.x - pizzaArr.get(i).x)) + Math.abs((point.y - pizzaArr.get(i).y)));
        }
        sum += dis;
      }
      ans = Math.min(ans, sum);
    } else {
      // 피자배열 길이에서 m개를 뽑는다
      for (int i = start; i < len; i++) {
        combi[level] = i;
        dfs(level + 1, i + 1);
      }
    }
  }

  static class Point {
    private final int x;
    private final int y;

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

    public int getX() {
      return x;
    }

    public int getY() {
      return y;
    }
  }
}