1. 문제 설명

문제 링크
크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.
배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.
예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

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

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

2. 풀이

주어진 배열을 주어진 조건에 따라 회전시켜 각 행의 합이 최소가 되는 명령어 순서를 찾는 것과 동일하다고 볼 수 있다.
위 문제를 살펴보면 3가지 기능이 필요한 것을 파악할 수 있다.
1. 명령어 실행 순서를 정하기 위한 기능
2. 주어진 명령어에 맞추어 사각형 영역을 회전시키는 기능
3. 명령어 실행이 끝난 후, 각 행의 합 중 최소값을 찾는 기능
1번은 쉽게 permutation을 떠올릴 수 있다. 명령어의 수 제한도 6이기 때문에 총 720가지의 경우 밖에 나오지 않는다.
2번은 한칸씩 이동을 시켜주면 간단하게 해결할 수 있다.
3번은 각 행의 합 중 최소값을 찾는 간단한 문제이다.
복잡해 보였던 문제를 3가지 part로 쪼개니 매우 쉬운 구현문제가 되었다!
이제 구현해보자!

3. 코드

python

from itertools import permutations  

# 명령어의 순서를 만드는 함수 
def make_permutation(K):
    instruction_numbers = [i for i in range(K)]
    permute = permutations(instruction_numbers, K)
    return permute

# 사각형을 회전시키기 위한 함수
def turning(grid, r, c, s):# 한칸씩 움직인다.
    # 한변의 길이 // 2 => 돌려야할 사각형 갯수
    num_of_box = (1 + (2*s)) // 2
    base_sx = r-1-s # 사각형 시작 좌표
    base_sy = c-1-s
    base_ex = r-1+s # 사각형 끝 좌표
    base_ey = c-1+s

    # 돌리기
    length = (1 + (2*s)) - 1
    for n in range(num_of_box):
        sx = base_sx + n
        sy = base_sy + n
        ex = base_ex - n
        ey = base_ey - n
        temp = grid[sx][sy]
        for i in range(length): grid[sx+i][sy] = grid[sx+1+i][sy]
        for i in range(length): grid[ex][sy+i] = grid[ex][sy+1+i]
        for i in range(length): grid[ex-i][ey] = grid[ex-i-1][ey]
        for i in range(length-1): grid[sx][ey-i] = grid[sx][ey-i-1]
        grid[sx][sy+1] = temp
        length -= 2

# 최소값을 찾기 위한 함수
def calc_min(N, M, grid):
    min_value = 100 * 60
    for n in range(N):
        value = sum(grid[n])
        if min_value > value:
            min_value = value
    return min_value

def main(N, M, K, grid, instructions):   
    # 1. 명령어 순서 만들기
    p_list = make_permutation(K)
    answer = 100 * 60
    for pl in p_list:
        temp_grid = [item[:] for item in grid]
        for instruction_number in pl:
            # 2. 돌리기
            r, c, s, = instructions[instruction_number]
            turning(temp_grid, r, c, s)
        # 명령어는 모두 소진 해야하기 때문에 다 돌린 후 계산
        # 3. 최소값 계산
        v = calc_min(N, M, temp_grid)
        if answer > v:
            answer = v
    return answer

# 디버깅용!
def Print(N, grid):
    for i in range(N):
        print(grid[i])

if __name__=='__main__':
    # 입력 받기
    N, M, K = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(N)]
    instructions = [list(map(int, input().split())) for _ in range(K)]
    answer = main(N, M, K, grid, instructions)
    print(answer)

4. 결과

간단하게 3 part로 나누어 쉽게 구현할 수 있는 문제였다. 하지만 중간에 첫번째 permutation 대로 실행 한후, 두번째 permutation을 실행 할 때 배열을 초기상태로 두어야 한다는 점을 간과해 2번의 제출 실패를 해버렸다. 출력초과 오류는 디버깅용 Print문을 지우지 않아서 생겼다. deepcopy 라이브러리를 활용할 수도 있지만 slicing 방식으로 원본 배열을 copy해 사용하는 방식으로 해결을 했다. 배열의 크기가 크지 않기 때문에 두 알고리즘의 속도 차이가 거의 없을 것 같았다. 어찌됬든, 생각보다 쉽게 해결할 수 있었다. 다만, 앞으로는 배열 값 복사에 주의하자!

KyungHyun Lim

BAEK17406 배열 돌리기4 (Python)

1. 문제 설명

2. 풀이

3. 코드

4. 결과