[백준] 15686 치킨배달

문제보기

삼성 역태 준비중!

여러개의 치킨 집 중 m개만을 살아남긴 채 치킨거리의 합을 구해야 하므로

조합이구만! 그럼 다음순열 함수를 써야겠군! 하면서 풀었던 문제…

import java.util.*;
import java.io.*;

public class Main{
	
  // 다음 순열을 만들어주는 함수 
  public static boolean next_perm(int[] arr){
    int i = arr.length -1; 
    while( i > 0 && arr[i-1] <= arr[i]){
      i--;
    }
    if(i <= 0){
      return false; 
    }
    int j = arr.length -1; 
    while( arr[j] >= arr[i-1] ){
      j--;
    }

    int temp = arr[j];
    arr[j] = arr[i-1];
    arr[i-1] = temp;

    int k = arr.length -1;
    while( i < k ){
      temp = arr[k];
      arr[k] = arr[i];
      arr[i] = temp;
      i++;
      k--;
    }
    return true; 
  }
  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int[][] map = new int[n][n]; 
    int[][] shop = new int[13][2]; // 치킨집의 x, y좌표를 담을 배열
    int sidx = 0; // 치킨집의 갯수

    for(int i = 0 ; i < n ; i++ ){
      st = new StringTokenizer(br.readLine());
      for(int j = 0 ; j < n ; j++ ){
        map[i][j] = Integer.parseInt(st.nextToken());
        if(map[i][j] == 2){ // 치킨집이면 따로 저장
          shop[sidx][0] = i;
          shop[sidx++][1] = j;
        }
      }
    }

    int[] sel = new int[sidx]; // 조합! sdix C m 을 수행해준다 
    for(int i = 0 ; i < m ; i++){ // 초기 수열
      sel[i] = 1;
    }
    int tot = 2000000000; // 치킨거리의 합의 최솟값을 담을 변수 
    do{
      int sum = 0; // 치킨거리 합 값을 담을 변수 
      for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
          if(map[i][j] == 1){ // 주택 발견!
            int min = 200; // 치킨거리를 담을 변수 
            for(int k = 0 ; k < sidx ; k++){ // 모든 치킨집에 대해서..
              if(sel[k] == 1){ // 모든 치킨집 중 살아남을 치킨집에 대해서..
                int r = shop[k][0];
                int c = shop[k][1];
                int d = Math.abs(i-r) + Math.abs(j-c); //문제에 나와있는 공식 그대로 사용
                if( d < min ){ // 가장 가까운 치킨집과의 거리만 min에 저장한다
                  min = d;
                }
              }
            }
            sum += min; // 치킨거리의 합에 더해준다
          }
        }
      }
      if(sum < tot ){ // 치킨 거리의 합의 최솟값이라면 tot에 저장
        tot = sum;
      }
    }while(next_perm(sel)); // 다음 순열 만들기 

    System.out.println(tot);

  }
}