자료구조 | 알고리즘/분할 정복(Devide Conquer)

분할정복 대표예시: L-트로미노 타일링(L-tromino) (예제: 백준 14601, 22359)

BE_개발자 2023. 10. 13. 02:05
728x90
반응형

분할 정복 알고리즘을 이용해 L - 트로미노 도형으로 정사각형을 채우는 문제를 풀 수 있다.

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8#/media/%ED%8C%8C%EC%9D%BC:Geometrical_dissection_of_an_L-triomino_(rep-4).gif

 

트로미노 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 모든 자유 트로미노 트로미노 (tromino) 또는 3-오미노 (3-omino)는 n=3인 폴리오미노로, 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형이다. 자유 트로미노 (fr

ko.wikipedia.org

위 사이트에 들어가면 L - 트로미노 도형으로 정사각형을 채우는 과정을 보여주는 이미지를 gif형식으로 보여준다.

 

이 페이지에서는 L - 트로미노 도형을 이용해 정사각형을 채우는 과정을 자세히 살펴본다.

예제로는 [백준 14061: 샤워실 바닥 깔기],   [백준 22359: 흔한 타일 색칠 문제]가 있다. 

 

1. 트로미노란?

아래의 그림처럼 정사각형 3개를 이어붙여 만든 도형을 말한다.

일자 모양의 트로미노 도형과 L자 모양의 트로미노 도형

트로미노 도형은 일자로 만든 도형과 L자로 만들어진 도형 두 가지가 존재한다.

 

2. L-트로미노 알고리즘

아이디어

[수학적 귀납법으로 모든 자연수에 대하여 참임을 확인]

L - 트트로미노 도형에 대하여 다음 명제가 성립한다. 

한 변의 길이가 2의 n승인 정사각형은 한 칸을 제외하고 모두 L-트로미노 도형으로 채울 수 있다

따라서 위의 명제만 증명하면 분할 정복 알고리즘으로 한 변의 길이가 2ⁿ인 정사각형을 한 칸을 제외하고 트로미노 도형을 채울 수 있다.

 

<증명>

1. n = 1일 때

크기가 2 x 2인 정사각형은 한 칸을 제외하고 L - 트로미노 도형으로 채울 수 있다

위의 그림에서도 알 수 있듯이 총 4가지의 방법으로 채울 수 있다.

 

2. n = k일 때


한 변의 길이가 2의 k승인 정사각형을 한 칸을 제외하고 모두 트로미노 도형으로 채울 수 있다고 가정하자.

 

3. n = k + 1일 때

바로 앞에서 한 변의 길이가 2의 k승인 정사각형들은 한 칸을 제외하고 모두 트로미노 도형으로 채울 수 있다고 가정했다.

n = k+1일 때에는 한 변의 길이가 2의 k승인 정사각형이 총 4개로 확장된다.

그러므로 n =  k+1일 때에는 위의 그림과 같이 크기가 1 x 1인 정사각형이 총 4개 생긴다.


따라서 1 x 1의 4칸에 L - 트로미노 도형을 채우게 되면 1 x 1의 빈 공간이 하나 남는다.

 

4. 결론

n = 1일 때에 참이고, n = k일 때 참이라고 가정했을 때에 n = k+1일 때에 참이므로 수학적 귀납법에 따라 모든 자연수 n에 대하여 참이다.

따라서 한 변의 길이가 2ⁿ인 정사각형은 한 칸을 제외하고 모두 L - 트로미노 도형으로 채울 수 있다.

 

[분할 정복 알고리즘]

하나의 문제는 두 개 이상의 부분 문제로 쪼갤 수 있다. 쪼개진 부분 문제는 다음 특징을 가진다.

  • 분할된 작은 문제는 원래 문제와 같은 해를 도출한다.
  • 분할된 문제는 최적 부분 구조를 갖는다.(서로 독립적이다)

따라서 재귀를 이용한 분할 정복 알고리즘으로 구현할 수 있다. 

이를 바탕으로 한 변의 길이가 2의 n승인 정사각형을 4등분하고 비어있는 3곳에 하나씩 공간을 채우고 난 다음 4등분된 영역에도 앞의 두 작업을 반복한다. 계속 진행되다 보면 한 변의 길이가 2인 정사각형까지 쪼개지고 마지막엔 한 칸을 제외한 모든 칸이 채워지게 된다.

 

 

 

알고리즘

[알고리즘의 순서]

  1. 정사각형을 1, 2, 3, 4구역으로 4등분한다.
  2.  1, 2, 3, 4구역을 탐색한 뒤 한 칸이라도 채워져 있는 영역을 찾는다.(한 구혁만 채워져 있고 나머지 세 영역은 비어이는 영역이 나온다)
  3. 한 칸이라도 채워져 있는 영역을 제외하고 나머지 세 영역에 L - 트로미노 도형의 모양대로 채운다.
  4. 1 ~ 3의 과정을 반복한다. 기저 사례는 한 변의 길이가 1일 때이다. 

 

[시뮬레이션]

한 변의 길이가 2의 n승인 정사각형을 4등분하고 비어있는 3곳에 하나씩 공간을 채우고 난 다음 4등분된 영역에도 앞의 두 작업을 반복한다. 계속 진행되다 보면 한 변의 길이가 2인 정사각형까지 쪼개지고 마지막엔 한 칸을 제외한 모든 칸이 채워지게 된다.

 

n = 2일 때 진행 부분 문제들이 반복되는 과정을 간단히 살펴보자.

위와 같이 1구역, 2구역, 3구역, 4구역으로 나눌 수 있다.(X는 채우지 못하는 한 칸이다)

그 다음 비어있는 세 곳에 L - 트로미노 도형을 채운다.

 1구역을 다시 1, 2, 3, 4구역으로 나누고 비어있는 세 부분에 L - 트로미노 도형을 채운다.

같은 과정을 귀납적으로 반복한다.

 2구역을 다시 1, 2, 3, 4구역으로 나누고 비어있는 세 부분에 L - 트로미노 도형을 채운다.

 3구역을 다시 1, 2, 3, 4구역으로 나누고 비어있는 세 부분에 L - 트로미노 도형을 채운다.

 4구역을 다시 1, 2, 3, 4구역으로 나누고 비어있는 세 부분에 L - 트로미노 도형을 채운다.

이렇게 한 변의 길이가 1일 때까지 위의 과정을 반복하면 총 5개의 L - 트로미노 도형이 채워지게 된다.

 

위에서 귀납적으로 증명했듯이,이 과정은 한 변의 길이가 2ⁿ인 모든 정사각형에 대해 똑같이 반복된다.

 

구현하기

크게 tromino함수와 check함수 두 가지가 쓰인다.

 

[tromino함수]

void tromino(int** map, int& num, int size, int x, int y) {
	if (size == 1) return;
	num++;
	size /= 2;
	x -= size;
	y -= size;

	pair<int, int> dir[4] = { {x, y}, {x+1, y}, {x, y+1}, {x+1, y+1} };

	bool pos1 = check(map, x - (size - 1), y - (size - 1), x, y);  // 1구역 탐색
	bool pos2 = check(map, x + 1, y - (size - 1), x + size, y);  // 2구역 탐색
	bool pos3 = check(map, x - (size - 1), y + 1, x, y + size);  // 3구역 탐색
	bool pos4 = check(map, x + 1, y + 1, x + size, y + size); // 4구역 탐색
	//빈곳 num표시
	bool pos[4] = { pos1, pos2, pos3, pos4 };
	for (int i = 0; i < 4; i++) {
		if (pos[i] == true)  map[dir[i].X-1][dir[i].Y-1] = num;
	}

	//이후 재귀 호출(분할 정복)   
	toumino(map, num, size, x, y);
	tromino(map, num, size, x + size, y);
	tromino(map, num, size, x, y + size);
	tromino(map, num, size, x + size, y + size);	
}
  1. 정사각형의 새로운 중심을 찾고, 4등분하여 구역을 나눈다.
  2. 4등분한 구역을 탐색한다.(check함수로 탐색)
  3. 숫자가 차있는 구역을 제외한 나머지 3구역(모두 비어있는 구역)에 숫자를 채운다.
  4. 이후 처음 나누어진 4구역에 대해 재귀호출을 실행한다.
  5. 기저 사례는 크기가 1일 때이다.

 

[check함수]

bool check(int** arr, int x1, int y1, int x2, int y2) {
	for (int i = x1; i <= x2; i++) {
		for (int j = y1; j <= y2; j++) {
			if (arr[i-1][j-1] != 0) return false;
		}
	}
	return true;
}
  1. 시작좌표와 끝좌표를 입력받고 탐색한다. 
  2. 하나라도 차있을 경우 false를 return받고 종료한다.
  3. 모두 비어있을 경우 true를 return받고 종료한다.

 

[기타]

  • 2차원 배열의 동적할당을 사용하여 좌표를 구현하였다.
  • 4등분된 구역의 탐색 결과는 pos의 배열을 만들어 비어있는지 여부를 확인하였다.
  • 정사각형의 중심을 기준으로 숫자를 채울 4구역은 pair의 형태로 배열을 만들어 저장하였다.
  • trumino함수가 종료할 때마다 num이 제대로 업데이트가 되지 않아서 num매개변수는 참조를 활용하였다. 

 

[전체 코드]

다음의 코드는 k를 입력받고, 빈칸의 좌표(m, n)을 입력받으면 그 칸을 제외하고 나머지 칸을 트로미노 알고리즘으로 탐색하고 숫자를 채워서 결과를 2차원배열로 출력해주는 코드이다.

/*trumino algorithm*************************************
1. 중심을 기준으로 1,2, 3, 4구역을 돌며 비어있는지 체크
2. 차있는 곳을 제외한 빈 구역 3곳을 하나씩 체크하기
3. 다시 재귀 호출 -> DFS의 탐색구조를 가짐
*******************************************************/
#define X first
#define Y second

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
using namespace std;
int siz;
int num;

//주어진 범위 (x1, y1) ~ (y1, y2)를 탐색하며 모두 비어있으면 true, 하나라도 차있으면 false
bool check(int** arr, int x1, int y1, int x2, int y2) {
	for (int i = x1; i <= x2; i++) {
		for (int j = y1; j <= y2; j++) {
			if (arr[i-1][j-1] != 0) return false;
		}
	}
	return true;
}

void tromino(int** map, int& num, int size, int x, int y) {
	if (size == 1) return;
	num++;
	size /= 2;
	x -= size;
	y -= size;

	pair<int, int> dir[4] = { {x, y}, {x+1, y}, {x, y+1}, {x+1, y+1} };

	bool pos1 = check(map, x - (size - 1), y - (size - 1), x, y);  // 1구역 탐색
	bool pos2 = check(map, x + 1, y - (size - 1), x + size, y);  // 2구역 탐색
	bool pos3 = check(map, x - (size - 1), y + 1, x, y + size);  // 3구역 탐색
	bool pos4 = check(map, x + 1, y + 1, x + size, y + size); // 4구역 탐색
	//빈곳 num표시
	bool pos[4] = { pos1, pos2, pos3, pos4 };
	for (int i = 0; i < 4; i++) {
		if (pos[i] == true)  map[dir[i].X-1][dir[i].Y-1] = num;
	}

	//이후 재귀 호출(분할 정복)   
	tromino(map, num, size, x, y);
	tromino(map, num, size, x + size, y);
	tromino(map, num, size, x, y + size);
	tromino(map, num, size, x + size, y + size);	
}


int main(void) {
	int k, m, n;
	cin >> k;
	siz = pow(2, k);
	int** map = new int* [siz];
	for (int i = 0; i < siz; i++) {
		map[i] = new int[siz];
		memset(map[i], 0, siz*4);
	}

	cin >> m >> n;  //(채워지지 않는 한 곳 입력)
	map[m-1][n-1] = -1;
	tromino(map, num, siz, siz, siz);

	for (int i = 0; i < siz; i++) {
		for (int j = 0; j < siz; j++) {
			cout << map[i][j] << "  ";
		}
		cout << "\n";
	}
	return 0;
}

[출력]

첫 번째 입력: k = 4, 채워지지 않는 칸: 5행 6열
두 번째 입력: k = 2, 채워지지 않는 칸: 1행 2열

 

3. 예제

기본 문제와 트로미노 알고리즘을 응용한 예제가 있다.

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

 

14601번: 샤워실 바닥 깔기 (Large)

첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K)

www.acmicpc.net

 

다음은 조금 응요해서 이웃한 도형은 색이 다르게 칠하는 문제이다.

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

 

22359번: 흔한 타일 색칠 문제

각 테스트 케이스마다 $2^k$개의 줄에 걸쳐 $2^k \times 2^k$개의 타일로 이루어진 정사각형 모양의 판에서 $a$번째 가로줄의 $b$번째 타일을 떼어냈을 때의 L-트로미노 색칠 방법을 출력한다. 이 중 $i$

www.acmicpc.net

 

4. 느낀점

분할 정복 알고리즘 중에선 난이도가 상당히 높은 예제인 것 같다. 이 알고리즘만 제대로 이해해도 거의 모든 분할 정복 문제들을 쉽게 풀 수 있을 것 같다.

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)