[BOJ 17406] 배열 돌리기4 - Python 풀이

링크

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[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의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

1 2 3 2 5 6 3 8 7 2 1 3 8 2 3 1 4 5 3 4 5 1 1 1 9 3 2 1 4 3	1 8 2 3 2 5 3 2 3 7 2 6 8 4 5 1 1 3 3 3 1 1 4 5 9 2 1 4 3 1	1 8 2 3 2 5 3 2 3 7 2 6 3 8 4 1 1 3 9 3 5 1 4 5 2 1 1 4 3 1
배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후
1 2 3 2 5 6 3 8 7 2 1 3 8 2 3 1 4 5 3 4 5 1 1 1 9 3 2 1 4 3	1 2 3 2 5 6 3 8 7 2 1 3 3 8 2 1 4 5 9 4 3 1 1 1 3 2 5 1 4 3	1 8 2 3 2 5 3 8 2 7 2 6 3 4 3 1 1 3 9 2 1 1 4 5 3 5 1 4 3 1
배열 A	(4, 2, 1) 연산 수행 후	(3, 4, 2) 연산 수행 후

배열 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

 

예제 입력 1

5 6 2
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
3 4 2
4 2 1

예제 출력 1

12

 

코드

import sys
from copy import deepcopy

N, M, K = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
calc = [tuple(map(int, sys.stdin.readline().split())) for _ in range(K)]
visited = [False] * K
result = float('inf')
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0] # 오, 아, 왼, 위

def in_range(x, y, s_x, s_y, s):
    return s_x <= x <= s_x+(2*s) and s_y <= y <= s_y+(2*s)

def rotate(tmp_arr, s_x, s_y, s):
        x, y = s_x, s_y
        dir, tmp = 0, tmp_arr[x][y] 
        while True:
            new_x, new_y = x+dx[dir], y+dy[dir]
            if not in_range(new_x, new_y, s_x, s_y, s): 
                dir = (dir + 1) % 4
                continue
            tmp_arr[new_x][new_y], tmp = tmp, tmp_arr[new_x][new_y]
            x, y = new_x, new_y
            if new_x == s_x and new_y == s_y: 
                break

def calculation(tmp_arr, order):
    for idx in order:
        r, c, s = calc[idx][0]-1, calc[idx][1]-1, calc[idx][2]
        s_x, s_y = r-s, c-s
        while s_x != r and s_y != c:
            rotate(tmp_arr, s_x, s_y, s)
            s_x, s_y, s = s_x+1, s_y+1, s-1

def get_val(tmp_arr):
    val = float('inf')
    for i in range(N):
        val = min(val, sum(tmp_arr[i]))
    return val

def backtracking(cnt, order):
    global result
    
    # cnt가 K가 되었을 때 한번에 order대로 rotoate
    if cnt == K:
        tmp_arr = deepcopy(arr)
        calculation(tmp_arr, order)
        result = min(result, get_val(tmp_arr))
        return
    
    for i in range(K):
        if visited[i]: continue
        visited[i] = True
        backtracking(cnt+1, order + [i])
        visited[i] = False
    
backtracking(0, list())
print(result)

 

결과

 

풀이

처음에 문제를 대충 보고 회전을 범위 내에서 가장 바깥 쪽에 있는 칸들만 회전하는줄 알았는데 코드를 다 짜고나서 알고 보니 그 안에 있는 칸들도 회전한다는 걸 깨달아서 조금 시간이 걸렸다 .. (문제를 제대로 읽자 .. 🥹)

 

일단 연산의 순서를 임의로 정할 수 있으며, 이 순서 중에서 연산한 결과의 최소값을 구해야 정답이 도출되므로 백트래킹을 사용한 브루트포스가 필요하다. 그리고 시뮬레이션 하는 과정에 필요한 배열은 deepcopy를 사용하여 arr에서 tmp_arr로 깊은 복사를 해주었다.

코드의 backtracking 함수에서 연산의 순서를 저장한 order 배열이 정해지면 calculation 함수를 통해 회전 연산을 한다.

연산은 초기에 r-s, c-s였던 s_x, s_y값이 r, c가 될 때까지 rotate 함수를 호출하여 회전연산을 하는 식으로 작동하는데, 이때 중요한 점은 s값이 매 회전 연산시마다 -1씩 줄어들어야 한다는 것이다.

왜냐하면 s_x, s_y값 처리는 매 회전 연산시마다 +1, +1씩 증가하므로 칸들의 범위도 이에 맞게 줄어들어야 하기 때문이다.

s_x, s_y값이 r, c 즉 칸 범위의 정중앙에 도착하면 더이상 회전 연산을 할 수 없으므로 calculation 함수를 빠져나오고, 그 뒤엔 get_val 함수가 호출되어 tmp_arr의 각 행의 합들의 최소값을 구한다.

그리고 구해진 최소값들을 global result값으로 갱신해주면 최종적으로 result값을 구할 수 있게 된다!

 

오랜만에 재밌는 문제였따~😋