[python] 17406번 배열 돌리기 4 백준 온라인 알고리즘 풀이

https://www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

from copy import deepcopy
N,M,K = map(int,input().split())
A = [ list(map(int,input().split())) for _ in range(N) ]
Q = [ tuple(map(int,input().split())) for _ in range(K)]
dx, dy = [1,0,-1,0], [0,-1,0,1]

ans = 10000

def min_row(arr):
    return min([ sum(i) for i in arr ])

def convert(arr, qry):
    r,c,s = qry
    r,c = r-1, c-1
    new_arr = deepcopy(arr)
    for i in range(1,s+1):
        sr, sc = r-i, c+i
        for w in range(4):
            for _ in range(i*2):
                nr, nc = sr + dx[w], sc + dy[w]
                new_arr[nr][nc] = arr[sr][sc]
                sr, sc = nr, nc
    return new_arr                

def dfs(arr,qry):
    global ans, Q
    if sum(qry) == K:
        ans = min(ans, min_row(arr))
        return

    for i in range(K):
        if qry[i]:
            continue
        new_arr = convert(arr, Q[i])
        qry[i] = 1
        dfs(new_arr, qry)
        qry[i] = 0

dfs(A,[0 for i in range(K)])
print(ans)

주어진 입력 양식

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

정답

12

6x6 배열일때 예시

0행, 0열 부터 시작이 아닌

1행, 1열을 예시로 들었고, 주어지는 쿼리도 함수를 돌릴땐, 아래 코드를 적용해줘야 한다.

r, c = r-1, c-1

중심을 A[3][4] 로 놨을때, 

대각선 방향으로 1칸 이동시 회전하고,

대각선 방향으로 2칸 이동하여 회전하는 것을 코드로 나타내면, 아래와 같이 나타낼 수 있다.

dx, dy = [1,0,-1,0], [0,-1,0,1]

for i in range(1,s+1):
        sr, sc = r-i, c+i
        for w in range(4):
            for _ in range(i*2):
                nr, nc = sr + dx[w], sc + dy[w]
                new_arr[nr][nc] = arr[sr][sc]
                sr, sc = nr, nc

또한, 배열을 돌면서 방향을 바꿔줘야 하기에 방향 벡터 dx, dy도  설정해준다.

대각선 방향으로 1칸 이동시 한 방향 벡터마다 2번 이동을하고

대각선 방향으로 2칸 이동시 한 방향 벡터마다 4번을 이동하므로

(i * 2)를 해주어 한 변의 이동을 나타내준다.

sr, sc = nr, nc

시작(start) index와  다음(next) index를 서로 바꿔줌으로써 다음칸 이동을 나타낸다.