[Algorithm/Divide&Conquer] 08. L-트로미노 타일링

트로미노 타일로 체스판 채우기

• 구멍이 하나 있는 정사각형 체스판을 L 자 모양의 트로미노(tromino) 타일로 채울 수 있는가?
  • 체스판의 크기를 2^k ×2^k 라 가정

 

 

접근

가장 작은 크기의 부문제인 “구멍이 하나 있는 2×2 체스판” 에 대해 어느 곳에 구멍이 있더라도 체스판을 채우는 것이 가능한가?

 

-->  “구멍이 하나 있는 2k×2k 체스판”에서 “구멍이 하나 있는 21×21 체스판”으로 문제를 점차 줄여나갈 수만 있다면 분할정복 알고리즘을 사용하여 해결 가능하다.

 

아이디어

• 정사각형의 체스판을 4개의 작은 체스판으로 나눈다
  • 하나의 2^k X 2^k 체스판 문제에서 4개의 2^(k-1) X 2^(k-1) 체스판 문제로 분할한다.
• 그런데, 3개의 2^(k-1) X 2^(k-1) 체스판에는 구멍이 없다.
  • 원래와 동일한 문제가 아니다

• 해결방안
  • 세 체스판에 걸치는 트리미노 타일을 체스판 중앙에 붙임
    • 구멍이라 가정
      • 원래와 동일한 문제로 바뀜
      • 4개의 순환 호출 가능

 

슈도 코드

체스판 크기: 𝑛 ∗ 𝑛 (단, n의 2의 지수승), 배열 board: 체스판, board[x][y] : 구멍 위치 라고 하자

void tile_board_DC(int board[ ][MAX], int n, int x, int y) {
	if (n == 2) 꼭 들어맞는 트로미노 타일을 붙임;
	else {
        board를 4등분하여 좌측상단부터 시계방향으로 board1
        ~board4라 함;
        board[x][y]를 포함하지 않는 3 체스판에 걸쳐 트로미노 타일을 붙이고
        타일의 각 위치를 구멍이라 가정;
        (x1,y1) = board1의 구멍 위치;
        (x2,y2) = board2의 구멍 위치;
        (x3,y3) = board3의 구멍 위치;
        (x4,y4) = board4의 구멍 위치;
        tile_board_DC(board1, n/2, x1, y1);
        tile_board_DC(board2, n/2, x2, y2);
        tile_board_DC(board3, n/2, x3, y3);
        tile_board_DC(board4, n/2, x4, y4);
	}
}

 

시간 복잡도

• 체스판의 차원 n을 기준으로 부문제는 4개이고 문제의 크기 𝑛은 절반으로 줄어듦 (𝑛 × 𝑛, 𝑛/2 × 𝑛/2, …)
  • O(logn)
• 순환호출 전 4개의 배열로 나누고 순환호출 후 배열 board로 모으는 작업이 필요하므로 분할과 결합에 체스판 원소 개수 𝑛 × 𝑛 에 비례하는 𝑂(𝑛^2)이 걸림
• 따라서 O(n^2 log n)

 

• 체스판의 지수인 k를 기준
• 부문제는 4개이고 문제의 크기 𝑘 는 1씩 줄어듦 (2^𝑘 ×2^𝑘,2^(𝑘−1) ×2^(𝑘−1), ...)
  • 즉, 𝑂(𝑘)
• 분할과 결합에 체스판 원소 개수 2^𝑘 ×2^ 𝑘 에 비례하는 Ɵ(2^(2k))이 걸린다
• 따라서 O(k*2^(2k))
  • k = log_2 (n) 을 대입하면 같은 결과를 얻는다

 

Ref) 알기쉬운 알고리즘