HW.2.3 트리미노 퍼즐

 처음 문제를 봤을 때 2차원 배열에 재귀로 패턴을 찍어낸다는 점에서 백준 별찍기 문제가 떠올랐다. 그 문제 역시실버 1난이도의 문제였음에도 재귀 동작의 복잡성 떄문에 제대로 이해하기 어려웠다. 풀이에 앞서 먼저 문제를 분석해봤다. 앞서 말했듯이 이 문제는 재귀함수를 통해 풀이한다. 기본 동작은 다음과 같다.

 

1. 이미 채워져 있는 점의 위치를 고려해 트리미노 하나를 놓는다.

2. 재귀의 depth를 검사한다.

3. 2번 step이 참이라면  1, 2, 3, 4분면을 분할정복한다.

 

1. 트리미노 하나를 놓을 수 있는 범위는 2x2이다. 이 2x2의 공간을 4분면의 축소라고 생각해보자. 채워져 있는 점 역시 2x2의 공간 안에 축소 시켜 표현할 때, 채워져 있는 점은 어디에 위치 하는지를 구해야한다. 그리고 이를 제외한 나머지 3칸을 cnt로 칠해주면 된다.

3. 채워져 있는 점이 x분면에 위치 한다면 x분면의 재귀호출을 할 때에는 자신이 가지고 있는 채워져 있는 점의 위치를 전달 해주어야 한다. 

다른 사분면의 경우는 처음 놓은 트리미노의 위치가 곧 해당 사분면의 채워진 점의 위치가 되고 이를 그대로 전달 해주면 된다.

 

#include<stdio.h>
#include<math.h>

int map[1025][1025];
int cnt;

void tromino(int m, int r, int c, int fr, int fc) {
  /*트리미노 하나 놓기*/
  cnt++;
  for(int i=0; i<2; i++) {
    for(int j=0; j<2; j++) {
      int row = r+m/2-1+i;
      int col = c+m/2-1+j;
      /*어디를 채우지 않을지 결정하기*/
      int frow = r+m/2-1+2*(fr-r)/m; 
      int fcol = c+m/2-1+2*(fc-c)/m;
      if(row == frow && col == fcol)
        continue;
      else
        map[row][col] = cnt;
    }
  }
  
  if(m>2) {
    int arr_r[4] = {r+m/2-1, r+m/2-1, r+m/2, r+m/2};
    int arr_c[4] = {c+m/2-1, c+m/2, c+m/2-1, c+m/2};
    int fquad = ((fc-c)/(m/2)) + 2*((fr-r)/(m/2)); //채워진 점의 사분면 결정하기
    /*채워진 점이 속한 사분면에 채워진 점의 위치 전달하기*/
    arr_r[fquad] = fr;
    arr_c[fquad] = fc;

    tromino(m/2, r, c, arr_r[0],arr_c[0]);
    tromino(m/2, r, c+m/2, arr_r[1],arr_c[1]);
    tromino(m/2, r+m/2, c, arr_r[2],arr_c[2]);
    tromino(m/2, r+m/2, c+m/2, arr_r[3],arr_c[3]);
  }
}

int main(void) {
  int n, fr, fc;
  scanf("%d %d %d",&n, &fr, &fc);
  int m = (int)pow(2,n);

  tromino(m, 0, 0, fr, fc);
  map[fr][fc] = 0;
  for(int i=0; i<m; i++) {
    for(int j=0; j<m; j++)
      printf("%d ",map[i][j]);
    putchar('\n');
  }

  return 0;
}