[Baekjoon] 배열 돌리기 6
Updated:
문제
크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분 배열의 크기는 2ℓ×2ℓ가 되어야 한다. 단계는 연산을 수행할때마다 정한다.
다음은 크기가 23×23 배열을 단계 ℓ의 값에 따라 부분 배열로 나눈 것이다. 같은 부분 배열은 같은 색상으로 표시했다.
| ℓ = 0 | ℓ = 1 | ℓ = 2 |
1번 연산은 각 부분 배열을 상하 반전시키는 연산이다.
| 배열 | ℓ = 1, 1번 연산 적용 |
2번 연산은 각 부분 배열을 좌우 반전시키는 연산이다.
| 배열 | ℓ = 2, 2번 연산 적용 |
3번 연산은 각 부분 배열을 오른쪽으로 90도 회전시키는 연산이다.
| 배열 | ℓ = 1, 3번 연산 적용 |
4번 연산은 각 부분 배열을 왼쪽으로 90도 회전시키는 연산이다.
| 배열 | ℓ = 2, 4번 연산 적용 |
5, 6, 7, 8번 연산은 부분 배열을 한 칸으로 생각하고 적용시킨다. 즉, 부분 배열의 안에 있는 값은 변하지 않는다.
5번 연산은 배열을 상하 반전시키는 연산이다.
| 배열 | ℓ = 2, 5번 연산 적용 |
6번 연산은 배열을 좌우 반전시키는 연산이다.
| 배열 | ℓ = 1, 6번 연산 적용 |
7번 연산은 오른쪽으로 90도 회전시키는 연산이다.
| 배열 | ℓ = 1, 7번 연산 적용 |
8번 연산은 왼쪽으로 90도 회전시키는 연산이다.
| 배열 | ℓ = 2, 8번 연산 적용 |
입력
첫째 줄에 N, R이 주어진다. 둘째 줄부터 2N개의 줄에 배열의 원소 A[i][j]가 주어진다. i번째 줄의 j번째 정수는 A[i][j]를 의미한다.
다음 R개의 줄에 배열에 적용시켜야 하는 연산이 한 줄에 하나씩 주어진다. 연산은 두 정수 k, ℓ로 이루어져 있고, k번 연산을 단계 ℓ로 적용한다는 의미이다.
출력
입력으로 주어진 배열에 R개의 연산을 순서대로 수행한 결과를 출력한다.
예제
Example 1:
Input:
3 8
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 1
2 2
3 1
4 2
5 2
6 1
7 1
8 2
Output:
64 63 62 61 60 59 58 57
56 55 54 53 52 51 50 49
48 47 46 45 44 43 42 41
40 39 38 37 36 35 34 33
32 31 30 29 28 27 26 25
24 23 22 21 20 19 18 17
16 15 14 13 12 11 10 9
8 7 6 5 4 3 2 1
Example 2:
Input:
3 4
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 0
2 0
3 0
4 0
Output:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Example 3:
Input:
3 4
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
5 0
6 0
7 0
8 0
Output:
64 63 62 61 60 59 58 57
56 55 54 53 52 51 50 49
48 47 46 45 44 43 42 41
40 39 38 37 36 35 34 33
32 31 30 29 28 27 26 25
24 23 22 21 20 19 18 17
16 15 14 13 12 11 10 9
8 7 6 5 4 3 2 1
Example4:
Input:
3 8
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 2
8 1
7 2
4 0
3 2
5 1
6 1
2 2
Output:
45 37 47 39 41 33 43 35
46 38 48 40 42 34 44 36
61 53 63 55 57 49 59 51
62 54 64 56 58 50 60 52
13 5 15 7 9 1 11 3
14 6 16 8 10 2 12 4
29 21 31 23 25 17 27 19
30 22 32 24 26 18 28 20
조건
시간 제한 : 1초
메모리 제한 : 512 MB
풀이과정
풀이 1
import sys
input = sys.stdin.readline
# n = , r = 연산 수
n, r = map(int, input().split())
graph = []
for _ in range(2**n):
graph.append(list(map(int, input().split())))
#graph = [[1,2,3,4,5,6,7,8], [9,10,11,12,13,14,15,16], [17,18,19,20,21,22,23,24],[25,26,27,28,29,30,31,32],
#[33,34,35,36,37,38,39,40],[41,42,43,44,45,46,47,48],[49,50,51,52,53,54,55,56],[57,58,59,60,61,62,63,64]]
for _ in range(r):
k, l = map(int, input().split())
l2 = 2**l
a = []
ngraph = [[0] * (2**n) for _ in range(2**n)]
# 1번 연산
if k == 1:
for i in range(0, 2**n, l2):
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
for k in range(len(a)//2):
a[k], a[-k-1] = a[-k-1], a[k]
for x in range(i, i+l2):
for y in range(j, j+l2):
ngraph[x][y] = a[x-i][y-j]
a = []
# 2번 연산
elif k == 2:
for i in range(0, 2**n, l2):
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
na = []
for aa in a:
na.append(aa[::-1])
a = []
for x in range(i, i+l2):
for y in range(j, j+l2):
ngraph[x][y] = na[x-i][y-j]
elif k == 3:
for i in range(0, 2**n, l2):
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
na = [[0]*l2 for _ in range(l2)]
for x in range(l2):
for y in range(l2):
na[x][y] = a[l2-y-1][x]
a = []
for x in range(i, i+l2):
for y in range(j, j+l2):
ngraph[x][y] = na[x-i][y-j]
elif k == 4:
for i in range(0, 2**n, l2):
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
na = [[0]*l2 for _ in range(l2)]
for x in range(l2):
for y in range(l2):
na[x][y] = a[y][l2-x-1]
a = []
for x in range(i, i+l2):
for y in range(j, j+l2):
ngraph[x][y] = na[x-i][y-j]
elif k == 5:
di = dict()
c = -1
for i in range(0, 2**n, l2):
c += 1
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
di[(i//l2, j//l2)] = a
a = []
for i in range(((2**n)//l2)//2):
for j in range((2**n)//l2):
di[(i, j)], di[(c-i,j)] = di[(c-i,j)], di[(i, j)]
for i in range(((2**n)//l2)):
for j in range((2**n)//l2):
aaa = di[(i, j)]
for a in range(i*l2, i*l2+l2):
for b in range(j*l2, j*l2+l2):
ngraph[a][b] = aaa[a-(i*l2)][b-(j*l2)]
elif k == 6:
di = dict()
c = -1
for i in range(0, 2**n, l2):
c += 1
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
di[(i//l2, j//l2)] = a
a = []
for i in range(((2**n)//l2)):
for j in range((2**n)//l2//2):
di[(i, j)], di[(i,c - j)] = di[(i,c - j)], di[(i, j)]
for i in range(((2**n)//l2)):
for j in range((2**n)//l2):
aaa = di[(i, j)]
for a in range(i*l2, i*l2+l2):
for b in range(j*l2, j*l2+l2):
ngraph[a][b] = aaa[a-(i*l2)][b-(j*l2)]
elif k == 7:
di = dict()
c = -1
for i in range(0, 2**n, l2):
c += 1
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
di[(i//l2, j//l2)] = a
a = []
ndi = dict()
for i in range(((2**n)//l2)):
for j in range((2**n)//l2):
ndi[(i, j)] = di[(c - j,i)]
for i in range(((2**n)//l2)):
for j in range((2**n)//l2):
aaa = ndi[(i, j)]
for a in range(i*l2, i*l2+l2):
for b in range(j*l2, j*l2+l2):
ngraph[a][b] = aaa[a-(i*l2)][b-(j*l2)]
elif k == 8:
di = dict()
c = -1
for i in range(0, 2**n, l2):
c += 1
for j in range(0, 2**n, l2):
for g in graph[i:i+l2]:
a.append(g[j:j+l2])
di[(i//l2, j//l2)] = a
a = []
ndi = dict()
for i in range(((2**n)//l2)):
for j in range((2**n)//l2):
ndi[(i, j)] = di[(j,c - i)]
for i in range(((2**n)//l2)):
for j in range((2**n)//l2):
aaa = ndi[(i, j)]
for a in range(i*l2, i*l2+l2):
for b in range(j*l2, j*l2+l2):
ngraph[a][b] = aaa[a-(i*l2)][b-(j*l2)]
graph = ngraph
for g in graph:
print(" ".join(map(str,g)))
Leave a comment