[백준] 15686번 치킨 배달

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/swtest/Q15686.java

일반 집(1)과 치킨 집(2)이 표시된 배열이 주어진다. 치킨 거리는 한 집과 치킨집 간의 거기들 중
가장 짧은 거리를 의미한다. 도시의 치킨 거리는 집들의 치킨 거리를 모두 더한 값이다.
M이 주어진다. M은 살아남은 치킨 집의 수이다. 최대 M개의 치킨 집을 살리고 모두 폐업시킬 때,
도시의 치킨 거리의 최소값을 구하여라.

처음 생각

치킨.. 치킨! 치킨은 언제나 옳다. 따라서 문제를 잘 풀어주어야 한다. 처음에는 치킨에 눈이 팔려서 각 집의 치킨 거리를 구하는 과정이 모든 치킨집과의 거리를 더해준 것으로 잘 못 풀었다.

▶ 예제가 잘 못 나오는 것을 보고, 바꿔주었다.

다음 생각

최대 M 개이므로 살아남는 치킨 집이 한 점포부터 M개의 점포까지 모든 경우의 수가 생긴다. 따라서 이 경우들을 모두 따져주어야 도시의 치킨 거리의 최소값을 계산할 수 있을 것이다.

▶ 따라서 K개의 치킨 집이 있다면 그 중, 1~M개의 치킨 집을 선택하여야 한다. 앞서 비트 마스크에 대한 글을 올렸으므로, 이번 문제도 비트 마스크를 이용하여 풀어보았다. 살짝 다른 점이 있다면 1~M개를 선택해야 하므로 0을 걸러주어야 한다.

다다음 생각

처음엔 치킨 집을 우선시 하여 치킨 집의 반복문을 앞서 작성하였는데 이렇게 작성시 일반 집의 반복문이 안으로 들어가 살아있는 모든 치킨 집에 대한 각 일반 집의 치킨 거리의 최소값을 저장해두기가 애매해진다.

▶ 배열을 사용할 수도 있지만 일반 집의 반복문을 앞서 작성하면, 한 집에 대해서 다음번 치킨 집 반복문에서 모든 치킨 거리를 구할 수 있기 때문에 이경우가 좀 더 효율적이다.

다다다음 생각

위에서 구한 각 집의 치킨 거리의 최소값을 모두 더하여 이를 최종 변수와 비교하면서 최소값을 도출해내었다.

방안

1) 비트 마스크를 안쓰다 쓰니깐 재귀보다 재미있는것 같다.

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

package baekjoon.swtest;   import java.util.ArrayList; import java.util.List; import java.util.Scanner;   public class Q15686 {     static int n,m;     static int[][] arr;     static List<Pair> list = new ArrayList<>();     static List<Pair> list2 = new ArrayList<>();     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         n = sc.nextInt();         m = sc.nextInt();         arr = new int[n][n];         // list는 치킨집         for(int i=0;i<n;i++) {             for(int j=0;j<n;j++) {                 arr[i][j] = sc.nextInt();                 if(arr[i][j]==2)                     list.add(new Pair(i, j));                 if(arr[i][j]==1)                     list2.add(new Pair(i,j));             }         }         solve();     }          private static void solve() {         int result = Integer.MAX_VALUE;         int size = list.size();         int size2 = list2.size();         for(int i=0;i<(1<<size);i++) {             // m개 이하로 선택하면              int cnt = Integer.bitCount(i);             // m이 1이상이므로 다 망할경우는 없다.             if(cnt==0) continue;             if(cnt<=m) {                 // 치킨 집들중에 거리가 가장 짧은게 치킨 거리                 int sum = 0;                 // 집(사람) 마다 생존한 모든 치킨집과 거리를 따져 최소값을 구해준다.                 for(int k=0;k<size2;k++) {                     // N이 최대 50일 경우, 49+49 = 98이므로 100으로 잡아주었다.                     int min = 100;                     for(int j=0;j<size;j++) {                         if(((1<<j)&i)>0) {                             // 집(사람)과 망하지 않을 치킨집의 거리 계산                             int t = Math.abs(list2.get(k).x-list.get(j).x)                                     +Math.abs(list2.get(k).y-list.get(j).y);                             // 그 집의 가장 짧은 치킨 거리 찾기                             if(min>t) min = t;                         }                     }                     // 집마다의 치킨 거리를 더해주기                     sum += min;                 }                 // 모든 도시의 치킨 거리의 최소 찾기                 result = Math.min(result, sum);             }         }         System.out.println(result);     }          static class Pair{         private int x,y;         Pair(int x,int y){             this.x = x;             this.y = y;         }     } }