BOJ 15686 치킨배달

15686번: 치킨 배달

 

처음에는 2차원 배열형태로 값이 주어져서 당연히 dfs나 bfs로 푸는 문제인줄 알았으나, 이 문제는 조합 알고리즘으로 푸는 문제였다.

 

조합 알고리즘만 있다면 매우 간단하게 구할 수 있다. 로직을 간단히 설명해보자면,

1. 치킨집과 가정집의 좌표를 배열에 저장해놓는다.

2. 주어진 치킨집으로 만들 수 있는 M개의 조합을 만들어서 각각 조합에서의 치킨거리를 구한후 , 가장 작은 것을 값으로 저장한다.

 

그러면 먼저 조합을 구하는 알고리즘부터 살펴보자.

 

private static void solution(int Idx, int Cnt) 
{
	if(Cnt==m) {
		ans=getMin(ans,getDistance());
		return;
	}
	
	for(int i = Idx; i<chiken_index;i++) 
	{
		if(checker[i]==true) continue;
		checker[i]=true;
		solution(i,Cnt+1);
		checker[i]=false;
	}
}

여기서 Idx는 이전에 선택된 인덱스이고, Cnt는 현재 몇번째를 뽑고 있는지를 나타낸다.  즉 몇번째 치킨집을 뽑고 있는지를 알려주고, 뽑힌 치킨집이 M (최대개수)와 같다면 멈춘 후, 해당 치킨집 조합의 치킨거리를 구한다.

 

여기서 chker[i]=true를 해주어서, 앞으로 만들어질 조합에 대해 '이 인덱스는 이미 뽑혔다'고 알려주고, solution 재귀함수가 모두 끝나면 checker[i]=false로 해주어, 이 후에 재귀가 다 끝난 후 만들어질 조합에서 또 뽑힐 수 있도록 해준다.

여기서 for문의 i가 Idx로 시작하는 것은, 조합의 특성 상, Idx 이전에 있는 값들은 뽑지 않기 때문이다. 

 

1 2 3 4

가 있고 원소가 2개인 조합을 만든다고 했을 때 

1 4 와 4 1 은 결국 똑같기 때문이다

 

 

그러면 이렇게 M개의 치킨집 조합을 구한 후, 각각의 가정집과 치킨집의 치킨거리를 구해야 한다.

이는 각각 가정집의 위치와, 선택된 치킨집 사이의 거리를 구한 후, 가장 작은 거리를 저장하면 된다. 이를 모든 가정집에 대해 실행하면 해당 조합에 대한 치킨 거리가 나온다. 

이렇게 구해진 치킨 거리를 모두 비교한 후, 가장 작은 값을 답으로 저장해주면 된다.

 

private static int getDistance() 
{
	int sum=0;
	int house_x;
	int house_y;
	int chiken_x;
	int chiken_y;
	int min;
	for(int i=0; i<house_index;i++) {
		min=9999999;
		house_x=house[i].x;
		house_y=house[i].y;
		for(int j=0; j<chiken_index;j++) {
			if(checker[j]==true) {
				chiken_x=chiken[j].x;
				chiken_y=chiken[j].y;
				min=getMin(min,Math.abs(house_x-chiken_x)+Math.abs(house_y-chiken_y));
			}
		}
		sum+=min;
	}
		
	return sum;
  }
	

 

 

 

전체 자바 소스이다.

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

class pair
{
	int x;
	int y;
	pair(int x, int y){
		this.x=x;
		this.y=y;
	}
}


public class Main {
	private static pair[] chiken;
	private static pair[] house;
	private static int house_index= 0;
	private static int chiken_index=0;
	private static boolean[] checker;
 	private static int m;
	private static int n;
	private static int ans=9999999;
	public static void main(String[] args)throws IOException
	{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int num;
		house = new pair[2*n];
		chiken = new pair[13];
		checker= new boolean[13];
		String[]s;
		for(int i = 0; i<n; i++) 
		{
			s = br.readLine().split(" ");
			for(int j = 0; j<n; j++) 
			{
				num = Integer.parseInt(s[j]);
				if(num==1) {
					house[house_index]=new pair(i+1,j+1);
					house_index++;
				}
				else if(num==2) {
					chiken[chiken_index]=new pair(i+1,j+1);
					chiken_index++;
				}
			}
		}
		
		solution(0,0);
		System.out.println(ans);
	}
	
	
	private static int getMin(int n, int m) 
	{
		if(n<m) return n;
		else return m;
	}
	
	private static int getDistance() 
	{
		int sum=0;
		int house_x;
		int house_y;
		int chiken_x;
		int chiken_y;
		int min;
		for(int i=0; i<house_index;i++) {
			min=9999999;
			house_x=house[i].x;
			house_y=house[i].y;
			for(int j=0; j<chiken_index;j++) {
				if(checker[j]==true) {
					chiken_x=chiken[j].x;
					chiken_y=chiken[j].y;
					min=getMin(min,Math.abs(house_x-chiken_x)+Math.abs(house_y-chiken_y));
				}
			}
			sum+=min;
		}
		
		return sum;
	}
	
	private static void solution(int Idx, int Cnt) 
	{
		if(Cnt==m) {
			ans=getMin(ans,getDistance());
			return;
		}
		
		for(int i = Idx; i<chiken_index;i++) 
		{
			if(checker[i]==true) continue;
			checker[i]=true;
			solution(i,Cnt+1);
			checker[i]=false;
		}
	}
}