04.08. 석판 나르기[Divide and conquer][백준 2339]

https://www.acmicpc.net/problem/2447

2447번: 별 찍기 - 10

 

Algorithm classification : Divide and conquer

 

04.08.1. Problem

I am trying to make a slab consisting of one or more impurities and gem crystals into several pieces and process it to obtain a higher value. At this time, in order to make a slab of high value, the slab must be divided into several pieces, each piece must be free of impurities and contain only one gem crystal.

In addition, in order to remove impurities from the slab, the slab must be cut around the point containing the impurities. Due to the texture of the slab, the slab can only be cut horizontally or vertically. When cutting a slab, it cannot be cut in the same direction as it was previously cut. (However, when first cutting, both horizontal and vertical directions are possible.)

Given the information on the impurities and gem crystals on the slab, calculate how many ways there are in total to divide the slab by removing the impurities from the slab, but so that each piece contains only one gem crystal.

The picture above shows the final divided slab when the slab is cut while removing impurities from the initial state of the slab. The gray line is a boundary cut horizontally or vertically with the impurity as the center, and the yellow color is a slab containing only one gem. When cutting the slab, No. ② or No. ③ cannot be cut in the same direction as in the direction of the previous cut, that is, No. ④ cannot be cut in the same direction as No. ②. Since it does not simply mean the cutting order, the direction of ④ may be the same as the direction of number 3.

The cut slab must be divided into two slabs. Also, it cannot be cut where there are crystals, and two or more crystals must not come to the final divided slab.

 

04.08.2. Input limit

The first line contains the size N (1 ≤ N ≤ 20) of the slab. The state of the slab is input from the next line to N lines. Here, 1 means impurities, 2 means gem crystals, and 0 means no impurities and gem crystals. At this time, the number of gem crystals does not exceed 15, and the information on the slab given in each line is separated by a single space.

 

04.08.3. Output

When dividing a given slab so that there is only one gem crystal without impurities in each slab, output how many cases exist in all. At this time, if no possible case exists, -1 is output.

 

04.08.4. Solution

제가 지금까지 소개해드렸던 분할 정복 문제 중에서는 아이디어 자체는 별 것 없지만 구현하기 가장 귀찮은 문제가 아닐까 합니다. 모든 Case를 다 시도해보시는 것이 중요합니다. 경우의 수에 대한 성질을 알고 계셔야 합니다. 고등학교 확률과 통계의 시간에서 Case를 Case 1과 Case 2로 나누면 전체 경우의 수는 n(Case 1) * n(Case 2)가 된다는 것을 배우셨을텐데 이를 주의하셔야 합니다. 이 문제에서 분할은 불순물을 기준으로 석판을 나누는 것이고 정복과정에서는 위에서 언급한 경우의 수 개념을 이용하시면 됩니다.

int cal(int s_x, int s_y, int e_x, int e_y, bool check){
	int i, j, temp, temp1, temp2;
	
	if(s_x > e_x || s_y > e_y)
		return 0;
	//printf("%d %d %d %d\n",s_x, s_y, e_x, e_y);
	temp1 = 0;
	temp2 = 0;
	for(i = s_x; i <= e_x; i++){
		for(j = s_y; j <= e_y; j++){
			if(a[i][j] == 1) //쓰레기 
				temp1++;
			else if(a[i][j] == 2) //보석 
				temp2++;
		}
	}
	if(temp1 == 0 && temp2 == 1) // 제대로 자른 경우  쓰레기는 없고 보석이 한개 일때 
		return 1;
	if(temp2 == 0 || (temp2 == 1 && temp1 > 0) || (temp2 > 1 && temp1 == 0)) // 제대로 못자른 경우 : 보석이 없음 or 보석이 1개이고 불순물 1개 이상 or 보석이 2개이상이고 불순몰 없음  
		return 0;
	
	temp = 0;

	if(check){
		//printf("%d %d\n",s_x, e_x);
		for(i = s_x; i <= e_x; i++){
			//printf("%d \n",i);
			temp1 = temp2 = 0;
			for(j = s_y; j <= e_y; j++){
				if(a[i][j] == 1)  
					temp1++;
				else if(a[i][j] == 2)
					temp2++;
			}
			if(temp1 && !temp2){
				//printf("-\n");
				temp += cal(s_x, s_y, i-1, e_y, !check) * cal(i+1, s_y, e_x, e_y, !check);	
				//printf("-\n");
			} 
		}
	}
	else{
		for(j = s_y; j <= e_y; j++){
			temp1 = temp2 = 0;
			for(i = s_x; i <= e_x; i++){
				if(a[i][j] == 1)  
					temp1++;
				else if(a[i][j] == 2)
					temp2++;
			}
			if(temp1 && !temp2){
				temp += cal(s_x, s_y, e_x, j-1, !check) * cal(s_x, j+1, e_x, e_y, !check);	
			} 
		}
	}
	return temp;
		
}

이번 code에서는 주석이 조금 달려있는데요. 중간에 제대로 coding하였는지 확인하기 위해서 단 것이니 크게 신경쓰지 않으셔도 됩니다. 중요한 것은 모든 Case를 고려하는 것인데요. 제대로 자른 경우는 쓰레기는 없고 보석이 한개 존재할 때입니다. 제대로 못자른 경우, 즉 경우의 수가 0이라 return 0을 하는 Case를 모두 고려하는 것은 조금 생각해보셔야 합니다. 보석이 없거나 보석이 1개이고 불순물이 1개 이상일 때, 보석이 2개 이상이고 불순물이 없을 때로 나눌 수 있습니다.(사실 1보석이 1개이고 불순물이 1개 이상인 경우는 다시 불순물을 기준으로 나누면 보석이 없는 경우가 생기니 고려를 하지 않아도 되지 않을까 생각하실 수 있습니다.)

 

또 한가지 고려해야 하는 것은 가로와 세로 모두 자를 수 있는 것입니다. 저같은 경우는 bool변수를 argument로 추가하였고요. main fuction에서도 호출할 때 고려해주었습니다. 사실 false, ture가 각각 세로인지 가로인지는 크게 의미부여를 할 필요가 없는게 위의 cal funtion에서 세로와 가로가 모두 구현되어 있기만 하면 됩니다. 즉, cal을 호출할 때 check의 값이 의미하는 바가 세로인지 가로인지 굳이 알 필요는 없습니다. 가로였다면 다음번에는 세로로 잘라야 하고 세로였다면 다음번에는 가로로 무조건 잘라야 하니까요.

	result = cal(0, 0, n-1, n-1, false);
	//printf("-----\n");
	result += cal(0, 0, n-1, n-1, true);
	printf("%d", result > 0 ? result : -1);

 

그 다음은 모든 경우를 고려해주는 것이 구현하기 까다로울 수 있습니다. 자르는 선에 쓰레기만 존재하는 지 확인을 해주면 됩니다. 그 후 모든 case를 더해주는데, 분할한 case를 다시 정복하면서 곱해주는거죠. 이 문제는 꽤 괜찮은 문제이니 한번 풀어보시길 추천드립니다.