[백준/20187] 종이접기 (Python)

Problem : https://www.acmicpc.net/problem/20187

20187번: 종이접기

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:28:15

 

---

 

문제 설명

 

 

정사각형의 종이를 중앙선을 중심으로 접는 방법은 아래 그림에서 보인 것처럼 4가지가 있다.

D: 가로 중심선을 중심으로 반으로 접되 윗 면이 아랫 면을 덮도록 접음

U: 가로 중심선을 중심으로 반으로 접되 아랫 면이 윗 면을 덮도록 접음

R: 세로 중심선을 중심으로 반으로 접되 왼쪽 면이 오른쪽 면을 덮도록 접음

L: 세로 중심선을 중심으로 반으로 접되 오른쪽 면이 왼쪽 면을 덮도록 접음

한 변의 길이가 2k인 정사각형 종이가 있을 때, 이를 세로로 k번, 가로로 k번 접으면 (접는 순서는 상관 없음) 각 변의 길이가 1인 정사각형이 된다. 아래 그림에서 보인 것처럼 각 변의 길이가 1인 정사각형의 네 귀퉁이 중 한 군데에 구멍을 낸다. 구멍의 위치는 그림에서 보인 것처럼 숫자로 표시한다.

구멍을 낸 후 접은 순서의 역순으로 종이를 펼치면, 종이에 2^2k개의 구멍이 있게 된다. 예를 들어, 한 변의 길이가 4(= 2^2)인 정사각형을 <R, D, D, R>순서대로 접은 후, 3번 위치에 구멍을 낸 다음 종이를 펼치면 아래 그림처럼 구멍이 나게 된다.

종이의 크기를 나타내는 정수 k, 종이를 접는 순서를 나타내는 정보, 구멍 뚫는 위치를 나타내는 정수가 주어질 때, 2^k × 2^k 격자에 뚫린 구멍의 위치를 출력하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

 

첫 번째 줄에 k가 주어진다.

다음 줄에는 종이 접는 방법을 나타내는 문자가 2k개 주어지는데, 각 문자는 공백으로 구분된다. 종이를 접는 방법 D, U, R, L은 각각 해당하는 대문자 알파벳으로 주어진다.

다음 줄에는 구멍 뚫는 위치를 나타내는 정수 h(0 ≤ h ≤ 3) 가 주어진다.

 

출력

 

접힌 종이를 접은 순서의 역순으로 펼친 후 정사각형에 뚫린 구멍의 위치를 번호로 출력한다. 출력은 총 2k줄로 이루어지며 i (1 ≤ i ≤ 2k)번째 줄에는 격자의 i번 행에 뚫린 구멍의 번호를 왼쪽에서 오른쪽 순서로, 공백을 사이에 두고 출력한다.

 

• 1 ≤ k ≤ 8
• 반드시 가로로 k번, 세로로 k번 접는다.

 

입력 예시

 

2
R D D R
3

 

출력 예시

 

0 1 0 1
2 3 2 3
0 1 0 1
2 3 2 3

 

 

---

 

풀이

 

일일히 매핑할 때, 총 경우의 수는

가 될 것이다. k = 8이므로 빠른 시간 내에 전부 해결할 수 있다. 즉 구현에 중점을 두도록 하자.

우선 최종 결과물부터 역순으로 계산할 수 있겠다. 즉 종이를 접는 방법을 역순으로 순회하며 매핑하는것이 포인트이다. 현재 종이의 가로 길이를 X, 세로 길이를 Y라 두자.

• 가로 접기를 기준으로 (x, y)번째 구멍은 (X-x, y)번째 구멍과 매핑된다. 또한 [0, 1, 2, 3]은 내부적으로 [1, 0, 3, 2]로 변환될 것이다.
• 세로 접기를 기준으로 (x, y)번째 구멍은 (x, Y-y)번째 구멍과 매핑된다. 또한 [0, 1, 2, 3]은 내부적으로 [2, 3, 0, 1]로 변환될 것이다.

이렇게 매핑된 새로운 2차원 행렬을 원본 행렬과 합치면 된다. 가로라면 X축에, 세로라면 Y축에 연결될 것이다. 또한 L, R, D, U 에 따라 원 2차원 행렬과 새 2차원 행렬의 연결 순서가 바뀜에 유의하자.

 

 

풀이 코드

import sys
input = sys.stdin.readline

dx = [1, 0, 3, 2]
dy = [2, 3, 0, 1]

K = int(input())
length = 2**K
fold_list = list(reversed(input().split()))
h = int(input())
x, y = 1, 1
answer = [[h]]

for fold in fold_list :
  tmp = [[-1]*x for _ in range(y)]
  for i in range(y) :
    for j in range(x) :
      if fold in ['L', 'R'] :
        tmp[i][j] = dx[answer[i][x-j-1]]
      else :
        tmp[i][j] = dy[answer[y-i-1][j]]

  if fold == 'L' :
    for i in range(y) :
      answer[i] += tmp[i]
    x *= 2
  elif fold == 'R' :
    for i in range(y) :
      answer[i] = tmp[i] + answer[i]
    x *= 2
  elif fold == 'U' :
    answer += tmp
    y *= 2
  else :
    answer = tmp + answer
    y *= 2

for _answer in answer :
  print(*_answer)

풀이 완료!