17406_배열 돌리기 4 (Python)

서정준·2022년 1월 4일
1

BAEKJOON

목록 보기
1/5
post-thumbnail

1. 아이디어

  • 먼저, 아래 코드로 구현한 이 문제의 시간 복잡도는 다음과 같다.
O(K!NMK)O(K!NMK) \\
{NM=배열의  크기(3N,M50)K=회전  연산의  개수(1K6)K!=순열의  가능한  개수\begin{cases} &NM = 배열의\;크기 \quad (3 ≤ N, M ≤ 50)\\ &K = 회전\;연산의\;개수 \quad \quad(1 ≤ K ≤ 6) \\ &K! = 순열의\;가능한\;개수 \end{cases}
  • 시작점 x,yx, y (아래 그림의 START)를 기준으로 시계방향으로 길이 2s2s (정사각형 한변)만큼 옮겨 준다.

    • 정사각형은 총 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

profile
통통통통

0개의 댓글