오늘은 민규가 훈련소에 입소하는 날이다. 모든 행사를 마치고 생활관으로 돌아와서 쉬려는데 갑자기 교관이 들어오더니 민규의 이름을 부르는 것이 아닌가. 당황한 채로 따라갔더니 이번엔 김준서를 아느냐고 물어보았다. 그 녀석이 샤워실 바닥을 깔았는데, 배수구 위치까지 막아버렸다면서 같은 학교 출신인 민규가 다시 깔라는 것이었다.
어떻게 타일을 깔지 고민하던 민규는 샤워실의 구조가 정사각형이면서 한 변의 길이가 2의 제곱수라는 사실을 알아냈다. 준서는 여기까지만 고려해서 2x2 크기의 타일로 바닥을 전부 채운 것 같은데, 문제는 이렇게 하면 배수구가 있어야 할 위치를 비울 수가 없다는 것이다. 이런저런 방법을 생각하다가 4칸을 차지하는 정사각형 타일 대신 3칸을 차지하는 ㄱ자 모양의 타일을 사용하면 될 것 같다는 느낌을 받았다.
그런데 ㄱ자 타일을 어떻게 채워야 할까? 생각하다 지친 민규는 여러분에게 이 방법을 찾아달라고 부탁했다. 첫날부터 생활관에서 밤을 새우는 일이 없도록 여러분이 도와주자.
첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 2) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2^K)가 공백으로 분리돼서 주어진다. 이때 가장 왼쪽 아래가 (1, 1), 가장 오른쪽 위가 (2^K, 2^K)이다.
출력
각 타일마다 고유한 번호를 매긴 타일의 배치도를 출력한다. 각 타일의 번호에는 19000 이하의 자연수만을 사용해야 한다. 배수구가 있는 위치는 -1로 표시한다. 가능한 답 중 하나만 출력하면 된다.
만약 알맞게 타일을 배치하는 방법이 존재하지 않는다면 -1을 출력한다.
입력 예시
1
2 2
출력 예시
1 -1
1 1
풀이
Large 기준 풀이법으로 작성해보도록 하자.
사실 위 그림에서 바로 알 수 있는 사실이 두 가지 존재한다.
큰 변의 길이가 2^k인 ㄱ자 블록 조합(단계 k의 ㄱ자 블록이라 칭하자)은 2^k - 1개의 ㄱ자 블록의 조합으로 대체 가능하다.
배수구의 위치는 사분면 기준 한 곳에 위치하므로, 배수구가 위치한 사분면을 제외한 구간을 ㄱ자 블록 조합으로 채우고 나머지를 재귀적으로 풀 수 있다.
즉 분할 정복을 적절히 사용하면 되는 문제이다. ㄱ자 블록 조합의 움푹 패인 방향을 dir로 두면, dir이 배수구가 위치한 사분면이 오도록 위치시키면 된다. 그리고 이 단계 k의 ㄱ자 블록은 (중앙의 단계 k-1개의 ㄱ자 블록 + dir을 제외하고 중앙으로 dir로 향하는 다른 사분면들의 단계 k-1개의 ㄱ자 블록 3개) 로 구성된다. 이런 식으로 분할하여 매핑하도록 처리하면 된다.
풀이 코드
N = int(input())
maps = [[0]*(1 << N) for _ in range(1 << N)]
tx, ty = map(int, input().split())
tx -= 1
ty = (1 << N) - ty
cnt = 1
def leftover(x, y, dir, depth) :
global cnt
if depth == 1 :
for i in range(2) :
for j in range(2) :
if i*2 + j == dir :
continue
maps[y+i][x+j] = cnt
cnt += 1
return
length = 1 << (depth - 1)
leftover(x + length // 2, y + length // 2, dir, depth-1)
for i in range(2) :
for j in range(2) :
new_dir = (i*2 + j)
if new_dir == dir :
continue
leftover(x + length * j, y + length * i, 3 - new_dir, depth - 1)
def div_and_con(x, y, depth) :
if not depth :
maps[y][x] = -1
return
length = 1 << (depth - 1)
for i in range(2) :
for j in range(2) :
dir = i*2 + j
ax = x + length * j
ay = y + length * i
if ax <= tx < ax + length and ay <= ty < ay + length :
div_and_con(ax, ay, depth-1)
leftover(x, y, dir, depth)
return
div_and_con(0, 0, N)
for _maps in maps :
print(*_maps)