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

#. Problem

https://www.acmicpc.net/problem/15686

* 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

 

먼저 단계별로 생각해보자.

1. 이중 반복문으로 map을 돌면서 집과 치킨집에 대한 동작을 해도 상관없겠지만,

   치킨집 좌표와 집의 좌표를 알고 있다면 이중 반복문으로 map을 돌지 않고도 해결할 수 있을 것 같다.

2. 어떤 치킨집을 선택할지 조합을 구해보자.

3. 치킨집을 모두 골랐을 때,

   각 집들로부터 선택된 치킨집까지의 가장 가까운 거리를 합해보자.

   도시에 있는 모든 집들로부터 선택된 치킨집들까지의 치킨 거리의 최솟값을 갱신해준다.

#. 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

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 BOJ15686 {       static int N, M, res = 987654321;     static ArrayList<Point> chicken, home;     static Point[] selected;          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());                  N = Integer.parseInt(st.nextToken());         M = Integer.parseInt(st.nextToken());         chicken = new ArrayList<>();         home = new ArrayList<>();         selected = new Point[M];                  for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             for (int j = 0; j < N; j++) {                 int val = Integer.parseInt(st.nextToken());                 // 치킨집 목록                 if(val == 2) chicken.add(new Point(i, j));                 // 집 목록                 if(val== 1) home.add(new Point(i, j));             }         }           selectChicken(0, 0);         System.out.println(res);     }       /**      * 치킨집을 선택하고, 모든 집들로부터 선택된 치킨집들까지의 가장 가까운 거리의 합 구하기       * @param start        조합의 시작점 인덱스      * @param cnt        현재까지 뽑은 조합의 개수      */     private static void selectChicken(int start, int cnt) {         // M개의 치킨집을 골랐을 때         if(cnt == M) {             // 도시의 모든 집에 대한 치킨 거리 정보             int all = 0;             // 도시의 모든 집들로부터             for (int h = 0; h < home.size(); h++) {                 int dist = 987654321; // 현재 집에 대한 정보                 // 선택된 치킨집들까지의 치킨 거리의 최솟값 연산                 for (int c = 0; c < M; c++) {                     int tmp = Math.abs(home.get(h).x - selected[c].x);                     tmp += Math.abs(home.get(h).y - selected[c].y);                     // 가장 가까운 거리를 찾자                     dist = Math.min(dist, tmp);                 }                 all += dist;             }             // 도시에 있는 모든 집들로부터 선택된 치킨집들까지의 치킨 거리의 최솟값             res = Math.min(res, all);             return;         }         // 더이상 고를 치킨집이 없을 경우         if(start == chicken.size()) return;                  // 조합 구하기         for (int i = start; i < chicken.size(); i++) {             // i index 치킨집 선택             selected[cnt] = chicken.get(i);             selectChicken(i + 1, cnt + 1);         }     } } Colored by Color Scripter

cs

조합을 구하는 방법은 두 가지 방법이 있다.

1.

start index부터 chicken.size()까지 시도하는데,

넘겨줄 때는 다음 index(i+1)를 넘겨준다.

// 조합 구하기 v1
for (int i = start; i < chicken.size(); i++) {
    // i index 치킨집 선택
    selected[cnt] = chicken.get(i);
    selectChicken(i + 1, cnt + 1);
}

2.

치킨집을 선택할 경우와

선택하지 않을 경우로 나누는 경우

selected[cnt] = chicken.get(start);
// start idx에 있는 치킨집을 선택할 경우
selectChicken(start + 1, cnt + 1);
// start idx에 있는 치킨집을 선택하지 않을 경우
selectChicken(start + 1, cnt);