[알고리즘] 15686. 치킨 배달

0. 문제

 

15686번: 치킨 배달

 

---

1. 문제 이해

 

• 최악의 경우 : 가정집(2 * 50), 치킨집(13 Combination 7 = 13! /(6! * 7!) = 1716) → 171,600 연산

 

171,600 연산은 아주 여유롭다. (1억 번 연산을 1초라고 가정)

 

완전탐색으로 푼다.

 

---

2. 제출

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int n, m, ret=Integer.MAX_VALUE;
    static List<Point> houses, chickens, comb; // 집, 치킨집, m개의 치킨집 조합
    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());

        houses = new ArrayList<>();
        chickens = new ArrayList<>();
        comb = new ArrayList<>();

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                int num = Integer.parseInt(st.nextToken());
                if(num==0) continue;
                else if(num==1) houses.add(new Point(i, j));
                else if(num==2) chickens.add(new Point(i, j));
            }
        }

//        System.out.println("houses : " + houses.size());
//        for(Point point : houses) {
//            System.out.println(point);
//        }
//        System.out.println("chickens : " + chickens.size());
//        for(Point point : chickens) {
//            System.out.println(point);
//        }

        solve(0, 0);
        System.out.println(ret);
        br.close();
    }

    public static void solve(int depth, int start){
        if(depth==m) {
            sumDis();
            return;
        }
        // 치킨집 m개 조합
        for(int i=start; i<chickens.size(); i++) {
            //System.out.println("I : " + i + " | chickens : "+chickens.size());
            comb.add(chickens.get(i));
            solve(depth+1, i+1);
            comb.remove(chickens.get(i));
        }
    }
    // 치킨집 조합에 따른 치킨 거리를 구하고
    public static void sumDis() {
        int sum = 0;
        //집마다 최소 치킨 거리 구하기
        for(Point house : houses) {
            int dis = Integer.MAX_VALUE;
            for(Point point : comb) {
                int tmp = 0;
                tmp += Math.abs(house.y - point.y);
                tmp += Math.abs(house.x - point.x);
                dis = Math.min(dis, tmp); // 집마다 최소 치킨 거리를 더한다.
            }
            sum += dis;
        }
        // 전체 치킨 거리 최소값 갱신
        ret = Math.min(ret, sum);
    }

    // 집, 치킨집에서 위치를 저장할 클래스
    static class Point {
        int y;
        int x;
        Point(int y, int x){
            this.y = y;
            this.x = x;
        }
//        @Override
//        public String toString() {
//            StringBuffer sb = new StringBuffer();
//            sb.append("y : ").append(this.y).append(" x : ").append(this.x);
//            return sb.toString();
//        }
    }

}

• 재귀함수를 통해 조합을 구현했다. O(N!) 시간복잡도를 가진다.
• Java는 만들어진 next_permutation 라이브러리가 없다…

 

---

 

(240225 추가)

 

비트마스킹을 이용해서 풀어보았다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

// 비트마스킹 사용
public class BOJ15686 {

	static int N, M, ret;
	static List<Point> homes, chickens;
	static final int HOME = 1, CHICKEN = 2;
	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());
		ret = Integer.MAX_VALUE;
		homes = new ArrayList<Point>();
		chickens = new ArrayList<Point>();
		
		for(int y=0; y<N;  y++) {
			st = new StringTokenizer(br.readLine());
			for(int x=0; x<N; x++) {
				int type = Integer.parseInt(st.nextToken());
				if(type == HOME) homes.add(new Point(y, x));
				if(type == CHICKEN) chickens.add(new Point(y, x));
			}
		}
		
		// 가능한 치킨집 조합을 모두 구하고 각각의 치킨 거리를 비교하여 최소 거리 ret를 구한다.
		solve(0, 0, 0);
		
		System.out.println(ret);
		br.close();
	}
	
	// 선택한 치킨집 조합을 비트마스킹으로 저장
	static void solve(int depth, int start, int vis) {
		if(depth == M) {
			ret = Math.min(ret, getDistance(vis));
			return;
		}
		
		int end = chickens.size();
		for(int i=start; i<end; i++) {
			solve(depth+1, i+1, vis | 1<<i);
			solve(depth, i+1, vis);
		}
	}
	
	static int getDistance(int vis) {
		int min = 0;
		int h_end = homes.size();
		int c_end = chickens.size();
		int dis; 
		for(int i=0; i<h_end; i++) { // 모든 집에 대하여
			dis = Integer.MAX_VALUE; 
			for(int j=0; j<c_end; j++) { // 모든 치킨집에 대하여
				if((vis & 1<<j) == 0) continue; // 선택하지 않은 치킨집 통과 
				int tmp = Math.abs(homes.get(i).y - chickens.get(j).y) + Math.abs(homes.get(i).x - chickens.get(j).x);
				dis = Math.min(dis, tmp); //각 집의 치킨 거리 구하기
			}
			min += dis; // 각 집의 치킨거리를 전체 치킨 거리에 더한다.
			if(min > ret) break; // 가지치기
		}
		return min;
	}
	
	static class Point {
		int y, x;
		
		Point(int y, int x){
			this.y = y;
			this.x = x;
		}
	}

}

 

---