https://www.acmicpc.net/problem/17470
공부 날짜 : 2023.02.16
정답 참조 여부 : O
배열을 연산 규칙에 맞게 돌린다. 배열과 연산과정이 입력으로 주어질때 연산 결과의 배열을 출력하는 문제이다.
구현만 하면 되지만, 최소한의 최적화가 필요한 문제이다.
구현 자체는 어렵지 않았다. 하지만 문제는 시간 초과 당연히 n*m의 배열을 R번 전부 연산하려면 각 연산마다 n*m의 연산이 필요하다(적은 경우도 있지만 최악의 경우만 고려) 따라서 연산의 결과에 의해 어떻게 변화하는지 최소한의 연산으로 구하고 변화의 결과를 배열로 복원하면 되는 문제였다.
연산은 4가지
상하 반전, 좌우 반전, 배열회전, 구간 회전
설명은 어렵기 때문에 결과만 말해주면
각각의 연산으로 구간들의 위치를 구해주고, 상하반전,좌우반전,배열회전에 의해 각 구간이 어떻게 변화하는지 계산을 따로 해줘야 했다.
우선 구간들의 연산은
1 2
3 4
에서 구간회전, 배열회전의 경우
3 1
4 2
가 되고 상하 반전, 좌우 반전은
3 4
1 2
가 되는 식으로
4개의 값만 바꿔서 연산을 최소화 시켜주었다.
그리고 상하반전, 좌우반전, 배열 회전의 경우 최종 결과의 회전 방향과, 반전여부만 확인했다.
나의 경우에는
result = [False, False, 0]으로 저장해서 배열을 회전시키면 result[2]의 값에 변화를 주고
상하반전시 result[0] = not result[0] 좌우 반전은 result[1] = not result[1]으로 처리 해줬다.
여기서 주의할점이 배열이 90도 회전된채로 반전을 시키면 상하반전이 좌우 반전이 되고 좌우반전이 상하 반전이 된다.
그 부분만 result[2] % 2 로 체크해주며 결과를 얻고 결과를 바탕으로 결과 배열을 복원해주니 정답으로 나왔다.
소스코드
from copy import deepcopy
import sys
input = sys.stdin.readline
##########################################
def cal_1():
if result[2] % 2:
result[1] = not result[1]
else:
result[0] = not result[0]
global sample_list
sample_list[0], sample_list[1] = sample_list[1], sample_list[0]
##########################################
def cal_2():
if result[2] % 2:
result[0] = not result[0]
else:
result[1] = not result[1]
sample_list[0][1], sample_list[0][0] = sample_list[0][0], sample_list[0][1]
sample_list[1][1], sample_list[1][0] = sample_list[1][0], sample_list[1][1]
##########################################
def cal_3():
result[2] = (result[2] + 1) % 4
cal_5()
##########################################
def cal_4():
result[2] = (result[2] - 1) % 4
cal_6()
##########################################
def cal_5():
global sample_list
new_sample = [[0, 0], [0, 0]]
new_sample[0][0] = sample_list[1][0]
new_sample[0][1] = sample_list[0][0]
new_sample[1][0] = sample_list[1][1]
new_sample[1][1] = sample_list[0][1]
sample_list = new_sample.copy()
##########################################
def cal_6():
global sample_list
new_sample = [[0, 0], [0, 0]]
new_sample[0][0] = sample_list[0][1]
new_sample[0][1] = sample_list[1][1]
new_sample[1][0] = sample_list[0][0]
new_sample[1][1] = sample_list[1][0]
sample_list = new_sample.copy()
##########################################
def turn_arr(arr):
new_arr = [[0 for _ in range(len(arr))] for _ in range(len(arr[0]))]
for i in range(len(arr[0])):
for j in range(len(arr)):
new_arr[i][j] = arr[len(arr) - j - 1][i]
return new_arr
##########################################
n, m, r = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
# 입력받은 리스트 구간을 1,2,3,4단위로 나누기
temp_list = [[[0 for _ in range(m//2)] for _ in range(n//2)]for _ in range(4)]
for i in range(n // 2):
for j in range(m // 2):
temp_list[0][i][j] = arr[i][j]
for i in range(n // 2):
for j in range(m // 2, m):
temp_list[1][i][j - m // 2] = arr[i][j]
for i in range(n // 2, n):
for j in range(m // 2):
temp_list[2][i - n // 2][j] = arr[i][j]
for i in range(n // 2, n):
for j in range(m // 2, m):
temp_list[3][i - n // 2][j - m // 2] = arr[i][j]
# for i in range(4):
# for j in temp_list[i]:
# print(j)
#
# print("#"*20)
##########################################
# 명령 입력받기
order = list(map(int, input().split()))
# 전체 배열을 돌리지 않고, 단순한 형태를 돌려서 결과만 복원하기
sample_list = [[0, 1], [2, 3]]
fun_list = [0, cal_1, cal_2, cal_3, cal_4, cal_5, cal_6]
result = [False, False, 0]
# 명령 수행
for i in order:
fun_list[i]()
##########################################
# 결과 복원
# 상하 반전
if result[0]:
for i in range(4):
temp_list[i].reverse()
# 좌우 반전
if result[1]:
for i in range(4):
for j in range(len(temp_list[i])):
temp_list[i][j].reverse()
# 배열 회전
for _ in range(result[2]):
for i in range(4):
temp_list[i] = turn_arr(temp_list[i])
answer = []
answer.extend(deepcopy(temp_list[sample_list[0][0]]))
answer.extend(deepcopy(temp_list[sample_list[1][0]]))
for i in range(len(answer) // 2):
answer[i].extend(temp_list[sample_list[0][1]][i])
answer[len(answer) // 2 + i].extend(temp_list[sample_list[1][1]][i])
for i in answer:
print(*i)