1. 아이디어

• 먼저, 아래 코드로 구현한 이 문제의 시간 복잡도는 다음과 같다.

• 시작점 $x, y$ (아래 그림의 START)를 기준으로 시계방향으로 길이 $2s$ (정사각형 한변)만큼 옮겨 준다.

  • 정사각형은 총 4변 이므로 4번 반복 한다.
  • 재귀를 이용하여 다음 START로 이동한 후 위의 과정을 반복한다.
    

2. 코드

import sys
import copy
from itertools import permutations

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

# 시계 방향으로 회전.
def rotate(x, y, s):
    if s == 0:
        return
    temp = a1[x][y]
    for dir in range(4):
        for _ in range(s * 2):
            x, y = x + dx[dir], y + dy[dir]
            temp, a1[x][y] = a1[x][y], temp
    rotate(x + 1, y + 1, s - 1)


n, m, k = map(int, input().split())
a0 = [list(map(int, input().split())) for _ in range(n)]
info = [list(map(int, input().split())) for _ in range(k)]
ans = sys.maxsize

for option in permutations(info, k):
    a1 = copy.deepcopy(a0)
    for r, c, s in option:
        rotate(r - (s + 1), c - (s + 1), s)
    for row in range(n):
        ans = min(ans, sum(a1[row]))
print(ans)

문제 출처

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