[백준/14600/14601] 샤워실 바닥 깔기 (Python)

Problem 1 : https://www.acmicpc.net/problem/14600

14600번: 샤워실 바닥 깔기 (Small)

 

Problem 2 : https://www.acmicpc.net/problem/14600

14600번: 샤워실 바닥 깔기 (Small)

 

Difficulty : Silver 1 (Small) / Platinum 5 (Large)

 

Status : Solved

 

Time : 00:29:41

 

---

 

문제 설명

 

 

오늘은 민규가 훈련소에 입소하는 날이다. 모든 행사를 마치고 생활관으로 돌아와서 쉬려는데 갑자기 교관이 들어오더니 민규의 이름을 부르는 것이 아닌가. 당황한 채로 따라갔더니 이번엔 김준서를 아느냐고 물어보았다. 그 녀석이 샤워실 바닥을 깔았는데, 배수구 위치까지 막아버렸다면서 같은 학교 출신인 민규가 다시 깔라는 것이었다.

어떻게 타일을 깔지 고민하던 민규는 샤워실의 구조가 정사각형이면서 한 변의 길이가 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)

풀이 완료!