백준 17406번 - 배열 돌리기 4(★★★ / ▲ / 1) : Python

기운찬곰·2021년 3월 29일

구현 백준 순열 완전탐색

백준2

목록 보기

12/17

개요

풀이 시간 : 40분
시간 제한 : 1초
메모리 제한 : 512 MB
기출 : baekjoon
링크 : https://www.acmicpc.net/problem/17406

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다. 다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

3 ≤ N, M ≤ 50
1 ≤ K ≤ 6
1 ≤ A[i][j] ≤ 100
1 ≤ s
1 ≤ r-s < r < r+s ≤ N
1 ≤ c-s < c < c+s ≤ M

해결방법

문제 이해하기

어우씨... 내가 싫어하는 유형 가운데 하나이다. 바로 인덱스 설정이 헷갈리는 문제... 특히 배열 회전... 매우 극혐한다. 조금만 잘못 설정해도 찾기가 무진장 어렵기 때문이다. 그리고 골치가 아프다. 주위가 조금이라도 시끄럽거나 집중이 안되면 풀기 어려운 문제이다.

알고리즘

일단 회전하는 방법은 사실 이전에 어떤 문제에서 봤었기 때문에 구현하는 방법은 대강 알 수 있었다. (어떤 문제더라... 음...)

회전 이동은 이런식으로 시켜주면 된다. 그리고 나서 그 상위에서도 똑같이 회전 이동을 반복 수행. 마지막으로 최솟값을 구해주면 끝이다.

Python

내 코드

from itertools import permutations
import sys

input = sys.stdin.readline
INF = int(1e9)

def part_rotate(board, rotate):
    for i in rotate:
        r, c, s = i
        for j in range(1, s + 1):
            cnt = 2 * j
            tmp = board[r - j][c + j]  # 가장 오른쪽 상위 값

            for k in range(cnt): # 위 : 왼쪽에서 오른쪽 이동(->)
                board[r - j][c + j - k] = board[r - j][c + j - k - 1]
            for k in range(cnt): # 왼쪽 : 아래쪽에서 위쪽으로 이동(^)
                board[r - j + k][c - j] = board[r - j + k + 1][c - j]
            for k in range(cnt): # 아래 : 오른쪽에서 왼쪽으로 이동(<-)
                board[r + j][c - j + k] = board[r + j][c - j + k + 1]
            for k in range(cnt - 1): # 오른쪽 : 위쪽에서 아래쪽으로 이동(v)
                board[r + j - k][c + j] = board[r + j - k - 1][c + j]

            board[r - j + 1][c + j] = tmp

    min_value = INF
    for i in range(n):
        min_value = min(min_value, sum(board[i]))

    return min_value


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    board = []
    for _ in range(n):
        board.append(list(map(int, input().split())))

    rotates = []
    for _ in range(k):
        r, c, s = map(int, input().split())
        rotates.append((r - 1, c - 1, s))

    # 순열
    min_value = INF
    for rotate in permutations(rotates):
        tempBoard = [[] * m for _ in range(n)]  # 임시 배열
        for i in range(n):
            for j in range(m):
                tempBoard[i].append(board[i][j])

        min_value = min(min_value, part_rotate(tempBoard, rotate))

    print(min_value)