백준- 15686 치킨 배달

www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

치킨집들중 M개를 골라 치킨 거리의 최솟값을 구하는 문제-> 조합

풀이1. 조합

** 주의 ** 치킨집, 집의 수가 일정하게 주어지는게 아님-> ArrayList 이용!!! 

배열로 풀다가 몇시간 날렸다.ㅋ

단, 리스트로 삽입할 시 **백트레킹** 필요하다.

---

////BJ 치킨배달
///*
// * 집,치킨집이 갖고있어야할것: 좌표 r,c
// * 도시의치킨거리=모든치킨거리 합
// * 집의치킨거리계산 = (최솟값)집거리 - 치킨집거리
// * 조합: 치킨집개수중에서 M개고르기
// * 구할것: (최솟값)도시의 치킨거리
// */
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 치킨배달_조합 {
    static int N;//배열의크기
    static int M;//고르는 치킨집의 수
    static int[][] map;
    static ArrayList<Point> chickens;//치킨집을 담을 어레이리스트--> 왜 배열말고 어레이리스트냐? 몇개를 담을지 모르므로
    static ArrayList<Point> houses;//집을 담을 어레이리스트
    static ArrayList<Point> selectChicken;//M개로 선택된 치킨집을 담을 어레이리스트
    static int minDist = Integer.MAX_VALUE;//최소 거리

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        //초기화
        map = new int[N + 1][N + 1];//맵 인덱스 1~N    
        chickens = new ArrayList<>();
        houses = new ArrayList<>();
        selectChicken = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1)houses.add(new Point(i, j));//i,j 좌표값만 저장하는건 같으므로 둘다 Point객체로 선언해준다.
                if (map[i][j] == 2)chickens.add(new Point(i, j));   
            }
        }
        select(0, 0);//M개를 고름

        System.out.println(minDist);//최소치킨거리를 출력
    }

    static void select(int start, int count) {
        if (count == M) {//M개를 뽑았으면 계산시작!
            calcDist();
            return;
        }

        for (int i = start; i < chickens.size(); i++) {
            selectChicken.add(chickens.get(i));//치킨집의 i번째를 담음
            select(i + 1, count + 1);//다음으로 보냄
            selectChicken.remove(selectChicken.size()-1);
            //돌아와서 빼고 다음으로 진행 --> ArrayList로 진행하려면 **백트레킹**이 필요하다!
        }
    }

    static void calcDist() {//최소 치킨거리를 구하기
    	//지역변수 2, static변수 1 개가 필요하다.
        int sum = 0;//치킨거리들의 누적함
        for (Point house : houses) {
            int min = Integer.MAX_VALUE;
            for (Point chicken : selectChicken) {
                int dist = Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y);//each집당 치킨집과의 최소 치킨거리
                min = Math.min(min, dist);//내 치킨거리가 기존 치킨거리보다 작다면 업데이트
            }
            sum += min;//각각 집들의 최소치킨거리를 더함 
        }
        minDist = Math.min(sum, minDist);//기존의 도시의 치킨거리와 현재 도시의 치킨거리값을 비교하여 업데이트.

    }

    static class Point {//좌표를 담을 객체.
        int x;
        int y;

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

---

풀이2. 비트마스크

---

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
////BJ 치킨배달
///*
//* 갖고있어야할것: 좌표 r,c
//* 도시의치킨거리=모든치킨거리 합
//* 집의치킨거리계산 = (최솟값)(집거리 - 치킨집거리)
//* 조합: 치킨집개수중에서 M개고르기
//* 구할것: (최솟값)도시의 치킨거리
public class 치킨배달_비트마스킹 {
    static int N;//배열의크기
    static int M;//고르는 치킨집의 수
    static int[][] map;
    static ArrayList<Point> chickens;//치킨집을 담을 어레이리스트--> 왜 배열말고 어레이리스트냐? 몇개를 담을지 모르므로
    static ArrayList<Point> houses;//집을 담을 어레이리스트

    static int minDist = Integer.MAX_VALUE;//최소 거리

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        //초기화
        map = new int[N + 1][N + 1];//맵 인덱스 1~N    
        chickens = new ArrayList<>();
        houses = new ArrayList<>();
        

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == 1)houses.add(new Point(i, j));//i,j 좌표값만 저장하는건 같으므로 둘다 Point객체로 선언해준다.
                if (map[i][j] == 2)chickens.add(new Point(i, j));   
            }
        }
        select();//M개를 고름

        System.out.println(minDist);//최소치킨거리를 출력
    }
    static ArrayList <Point> selectChicken;
    static void select() {

       for(int i=0; i < (1<< chickens.size()); i++) {
    	   //비트마스킹으로 조합을 뽑기 때문에 ArrayList를 새로 갱신해주면서 반복문 진행. 
    	   //비트마스크 -> 반복문
    	   selectChicken = new ArrayList<>(); 
    	   for (int j = 0; j < chickens.size() ; j++) {
    		   
			if( (i & ( 1<<j )) !=0) {
				 selectChicken.add(chickens.get(j));			
			}
    	   }
    	  if(selectChicken.isEmpty()) continue; //아무것도 고르지 않았다면 계속
    	  if(selectChicken.size() >M) continue; //고른 수가 M을 넘어갔다면 계속
    	  //왜 체크하냐? -> 모든 경우의 수를 다 따져볼거니까
    	  //i가 끝날때 함수 실행.
    	  calcDist();
       }

    }
    //조합풀이와 동일
    static void calcDist() {//최소 치킨거리를 구하기
    	//지역변수 2, static변수 1 개가 필요하다.
        int sum = 0;//치킨거리들의 누적함
        for (Point house : houses) {
            int min = Integer.MAX_VALUE;
            for (Point chicken : selectChicken) {
                int dist = Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y);//each집당 치킨집과의 최소 치킨거리
                min = Math.min(min, dist);//내 치킨거리가 기존 치킨거리보다 작다면 업데이트
            }
            sum += min;//각각 집들의 최소치킨거리를 더함 
        }
        minDist = Math.min(sum, minDist);//기존의 도시의 치킨거리와 현재 도시의 치킨거리값을 비교하여 업데이트.

    }

    static class Point {//좌표를 담을 객체.
        int x;
        int y;

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

 

---

출력

 

비트마스크가 크기 제한 외라면 시간,메모리 면에서 우수하다고 알고 있는데 왜 시간이 비슷한지는 의문이다. 

반복문을 사용해서 그럴거라고 추정 중