[백준] 17406 배열 돌리기 4

문제

• NxM 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다.
  • 3 <= N, M <= 50
• 배열은 회전 연산을 수행할 수 있다.
  • (r, c, s) 에서 (r-s, c-s) ~ (r+s, r+s) 까지 정사각형을 시계 방향으로 한 칸씩 돌린다.
• 배열 A와 가능한 회전 연산이 K개 주어졌을 때, 배열 A의 최솟값 구하기
  • 회전 연산은 모두 한 번씩 사용해야 하고, 순서는 임의로 정해도 된다.
  • 1 <= K <= 6

 

풀이

• 완전 탐색
  • 전체 연산의 가능한 모든 순서 조합으로 회전한 뒤의 최솟값 비교하기
• 시간 복잡도 : 6! * 50*50  => 가능!
  • 회전 연산 K의 순서 : 6! 
  • 각 회전 연산을 수행 시 : 최대 50*50 

import sys
sys.setrecursionlimit(10**4)

# 행렬 rotate 
def rotate(r, c, s, A):
    rs, re, cs, ce = r-s, r+s, c-s, c+s
    new_A = [row[:] for row in A]   # rotate 후 행렬 
    while rs != r :
        # 첫 행
        new_A[rs][cs] = A[rs+1][cs]
        for col in range(cs+1, ce+1): 
            new_A[rs][col] = A[rs][col-1]
        # 중간 행
        for row in range(rs+1, re):
            new_A[row][cs] = A[row+1][cs]
            new_A[row][ce] = A[row-1][ce]
        # 마지막 행
        for col in range(cs, ce): 
            new_A[re][col] = A[re][col+1]
        new_A[re][ce] = A[re-1][ce]

        rs, re, cs, ce = rs+1, re-1, cs+1, ce-1
    return new_A

# 연산 순서별로 확인하기
def solve(n, rots, A):
    global answer
    if n == 0 :     # 전체 회전 연산 끝나면 최솟값 비교
        answer = min(answer, min([sum(row) for row in A]))
    else:
        for i in range(n):
            new_A = rotate(*rots[i], A)
            solve(n-1, rots[:i]+rots[i+1:], new_A)
        
# 입력 받기
N, M, K = map(int, input().split())
A = []
for _ in range(N):
    A.append(list(map(int, input().split())))

rots = []
for _ in range(K):
    r, c, s = list(map(int, input().split()))
    rots.append((r-1, c-1, s))
    
answer = 1e9
solve(K, rots, A)
print(answer)

 

References

• 백준 17406
• 2023.05.02 오늘의 문제