타일채우기 재귀 알고리즘

10*10의정사각형에 4*2직사각형, 2*2 정사각형, 4*4 정사각형을 무한하게 사용해서 꽉 채우는 경우의수

 

코딩테스트에서 정해진규격의 도형들로 빈공간을 채우는 경우의 수를 구하는 문제가 나왔다!

재귀함수를 많이 사용해본 경험이 없어서 알기가 쉽지 않았다..

 

프로그램의 실행 과정 요약

1. 10x10 보드의 맨 위 왼쪽(좌표 0,0)에서 시작하여 타일을 놓을 수 있는지 확인
2. 타일을 놓을 수 있으면 해당 영역을 타일로 채우고, 그다음 칸으로 재귀적으로 이동
3. 보드가 다 채워지면 경우의 수를 1 증가시키고, 타일을 다시 제거하여 다음 가능한 배치를 탐색
4. 이 과정을 통해 가능한 모든 타일 배치 경우의 수를 구한다.

여기서 중요하게 봐야할 코드는 fill과 countWays함수이다.

좌표 (0,0)에서 시작해 하나의 타일을 채우고 아래로 내려가면서 재귀함수를 통해 계속 다양한 타일을 채워넣으며 경우의 수를 확인해 나아간다.

그렇게 y축에 더이상 타일을 놓지 못하면 다음 x축으로 이동한다 (x+1)

 

즉,  0,0 에 3가지의 타일을 둔 이후에 아래로 내려가며 또한번 3가지의 타일을 놓을 수 있는가를 확인을 하며 보드 전체가 다 채워질때까지 재귀함수를 실행시킴으로써 모든 빈공간을 채울 수 있는 경우의 수를 찾을 수 있다.

public class Tiling {

	//
    static int countWays(int[][] board, int x, int y) {
        // 만약 끝까지 도달했으면 카운트를 1 증가
        if (x == 10) {
            return 1;
        }
        // 행 끝에 도달했으면 다음 행으로 이동
        if (y == 10) {
            return countWays(board, x + 1, 0);
        }
        // 이미 채워진 경우 다음 칸으로 이동
        if (board[x][y] != 0) {
            return countWays(board, x, y + 1);
        }

        int ways = 0;

        // 4x2 직사각형 타일을 놓을 수 있는지 확인하고 놓기
        if (y + 1 < 10 && x + 3 < 10 && isFree(board, x, y, 4, 2)) {
            fill(board, x, y, 4, 2, 1);
            ways += countWays(board, x, y + 2);
            fill(board, x, y, 4, 2, 0); // 원상복구
        }

        // 2x2 정사각형 타일을 놓을 수 있는지 확인하고 놓기
        if (y + 1 < 10 && x + 1 < 10 && isFree(board, x, y, 2, 2)) {
            fill(board, x, y, 2, 2, 1);
            ways += countWays(board, x, y + 2);
            fill(board, x, y, 2, 2, 0); // 원상복구
        }

        // 4x4 정사각형 타일을 놓을 수 있는지 확인하고 놓기
        if (y + 3 < 10 && x + 3 < 10 && isFree(board, x, y, 4, 4)) {
            fill(board, x, y, 4, 4, 1);
            ways += countWays(board, x, y + 4);
            fill(board, x, y, 4, 4, 0); // 원상복구
        }

        return ways;
    }

    // 주어진 타일을 배치할 수 있는지 확인
    static boolean isFree(int[][] board, int x, int y, int h, int w) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (board[x + i][y + j] != 0) {
                    return false;
                }
            }
        }
        return true;
    }

    // 보드에 타일을 채우거나 제거
    static void fill(int[][] board, int x, int y, int h, int w, int value) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                board[x + i][y + j] = value;
            }
        }
    }

    public static void main(String[] args) {
        int[][] board = new int[10][10]; // 10x10 보드 초기화
        System.out.println("Number of ways to tile the board: " + countWays(board, 0, 0));
    }
}