[SWEA] 10888. 음식배달(조합).java

#. Problem

https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AXUqw9zKYaoDFASe&categoryId=AXUqw9zKYaoDFASe&categoryType=CODE

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

[BOJ] 15686. 치킨 배달(조합).java

위 문제와 유사한 문제다.

1개 ~ 선택할 수 있는 최대 음식점 개수(n)만큼 시도를 해볼 것이다.

선택할 수 있는 n개의 음식점을 조합으로 선택한 후,

각 집으로부터 가장 가까운 음식점과의 배달 거리를 누적한다.

모든 집 ~ 음식점과의 배달거리를 더했다면,

마지막으로, 누적된 배달거리 + 운영비의 합이 최소인 해를 찾으면 된다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer;   public class SWEA10888 {       static int N, sel[], res;     static ArrayList<Point> restaurant, house;     static ArrayList<Integer> feeList;          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;           int T = Integer.parseInt(br.readLine());         for (int tc = 1; tc <= T; tc++) {                          N = Integer.parseInt(br.readLine());             res = Integer.MAX_VALUE;             restaurant = new ArrayList<>();             feeList = new ArrayList<>();             house = new ArrayList<>();                          for (int i = 0; i < N; i++) {                 st = new StringTokenizer(br.readLine());                                  for (int j = 0; j < N; j++) {                     int a = Integer.parseInt(st.nextToken());                     // 집 위치 저장                     if(a == 1) house.add(new Point(i, j));                     // 음식점 위치 및 정보 저장                     else if(a >= 2) {                         restaurant.add(new Point(i, j));                         feeList.add(a);                                             }                 }             }                          // 조합으로 치킨집을 선택해보자.             for (int i = 1; i <= restaurant.size(); i++) {                 sel = new int[i];                 comb(0, i, 0, 0);             }                          System.out.println("#" + tc + " " + res);         }              }       private static void comb(int idx, int n, int cnt, int fee) {                  // 모든 음식점을 선택했다면         if(cnt == n) {             int tmpRes = 0;             // 각 집에서 가장 가까운 음식점과의 배달 거리             for (Point now : house) {                 int minDist = Integer.MAX_VALUE;                 // restaurant List                 for (int i = 0; i < n; i++) {                     int dist = Math.abs(restaurant.get(sel[i]).x - now.x) +                              Math.abs(restaurant.get(sel[i]).y - now.y);                                          minDist = Math.min(minDist, dist);                 }                 tmpRes += minDist;             }             // 운영비 합의 최소             res = Math.min(res, tmpRes + fee);                          return;         }         // 더이상 선택할 수 있는 치킨집이 없을 경우          if(idx == restaurant.size()) return;                  for (int i = idx; i < restaurant.size(); i++) {             sel[cnt] = i;             comb(i + 1, n, cnt + 1, fee + feeList.get(i));                      }              }   }   Colored by Color Scripter

cs