[백준] 배열 돌리기 4

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

 

1. 문제 이해

(r, c)를 중심으로 가장 왼쪽 위가 (r - s, c - s)이고 오른쪽 아래가 (r + s, c + s)가 왼쪽 아래인 정사각형을 돌리는 회전연산이 주어집니다. 임의의 순서로 K개의 회전연산을 수행했을 때 행의 합이 최소를 구하는 문제입니다.

2. 문제 접근

deque를 이용한 구현으로 풀이하였습니다. permutation을 통해서 회전연산의 순서를 정해주고 deque를 통해 각각의 정사각형을 회전시켜준 다음 행의 총합을 구하는 방식으로 풀이하였습니다.

3. 풀이

import sys
from itertools import permutations
from collections import deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m, k = tuple(map(int, input().split()))

board = [
    list(map(int, input().split()))
    for _ in range(n)
]

saved = [
    [0] * m
    for _ in range(n)
]

for i in range(n):
    for j in range(m):
        saved[i][j] = board[i][j]

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

def rotate(y, x, n):
    global board

    q = deque([board[y][x]])
    pos = deque([(y, x)])

    dir = 0
    for i in range(4):
        cnt = 0
        while cnt < n:
            y += dy[dir]
            x += dx[dir]
            pos.append((y, x))
            cnt += 1

            q.append(board[y][x])
        dir += 1

    q.pop()
    pos.pop()


    q.appendleft(q.pop())

    for y, x in pos:
        board[y][x] = q.popleft()

arr = [x for x in range(k)]

rotate_info = [
    tuple(map(int, input().split()))
    for _ in range(k)
]

MAX = 50 * 50 * 100 + 1000
ans = MAX

for p in list(permutations(arr)):
    min_of_rotate = MAX
    # 원상 복구
    for i in range(n):
        for j in range(m):
            board[i][j] = saved[i][j]

    for i in range(k):
        r, c, s = rotate_info[p[i]]

        r -= 1
        c -= 1

        for j in range(s):
            rotate(r - j - 1, c - j - 1, (j + 1) * 2)

    for row in board:
        min_of_rotate = min(sum(row), min_of_rotate)

    ans = min(ans, min_of_rotate)

print(ans)

4. 회고

임의의 순서로 회전한다는 지문을 읽지 못해서 한번 틀렸습니다. 지문을 꼼꼼히 읽어야함을 느꼈습니다.