[BOJ] 17406. 배열 돌리기 4.py

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

- 회전 연산은 세 정수 (r, c, s)

-  가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다

- 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

query의 순서는 상관이 없다고 하였으므로, 

K!만큼의 경우의 수를 연산해주여야 한다.

그리고

가장 왼쪽 윗 칸의 정보(r-s, c-s)와 가장 오른쪽 아랫 칸 정보(r+s, c+s)로 배열을 회전시켜야 한다.

한 지점을 정하고 동작시키는게 편할 것 같다.

만약 우측 상단을 기준으로 잡는다면

하좌상우로 쭉쭉 밀릴것이다.

이 문제도 결국 해결을 못 하고 강사님 힌트를 얻고 해결했는데..

빨리 이 난이도의 문제도 술술 풀렸으면..

내일 C++로 다시 풀어봐야겠다.

#. Python

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

from copy import deepcopy   dx, dy = [1, 0, -1, 0], [0, -1, 0, 1]   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)]   rst = 10000   def MinVal(arr):     return min([sum(lst) for lst in arr])   def Rotate(arr, qry):     (r, c, s) = qry     r, c = r-1, c-1     new_arr = deepcopy(arr)     for i in range(1, s+1):         rr, cc = r-i, c+i         for w in range(4):             for d in range(i*2):                 rrr, ccc = rr + dx[w], cc + dy[w]                 new_arr[rrr][ccc] = arr[rr][cc]                 rr, cc = rrr, ccc     return new_arr   def DFS(arr, qry):     global rst     if sum(qry) == K:         rst = min(rst, MinVal(arr))         return     for i in range(K):         if qry[i]:             continue         new_arr = Rotate(arr, Q[i])         qry[i] = 1         DFS(new_arr, qry)         qry[i] = 0   DFS(A, [0 for i in range(K)]) print(rst) Colored by Color Scripter

cs

line 39) 회전 연산 개수를 크기로 갖는 list를 DFS에 넘겨주며 시작

    (이 list는 사용된 query와 사용되지 않은 query를 구분하기 위한 list)

line 26~37) 회전 연산을 수행하는 방법은 수열을 미리 계산한 후 진행하기도 하지만
              DFS를 활용하여 더 빨리 해결할 수 있다고 한다.

line 28~30) 입력된 회전 연산이 모두 사용되었을 경우

line 29) 최소값을 저장한 후 재귀함수 return

line 31~37) 연산 개수만큼 반복

line 32~33) 이미 사용된 연산이라면 continue

line 34) 배열을 회전시킨 후 new_arr에 저장

line 35) 해당 query를 사용하였으므로 체크한 후 DFS에 새로운 배열을 넣고 호출

line 37) DFS() 동작을 마쳤으므로 query사용을 해제

line 13~24) 배열을 회전시켜주는 함수

line 14) 들어온 회전 연산을 분리

line 15) (0,0) 기준으로 배열이 저장되어있으므로 1씩 빼준다.

line 16) 회전시키면서 원본 배열을 활용하여 값을 입력해주기 위해 원본 배열 복사

line 17) 중심으로부터 s겹이 회전하게 된다.

line 18) 다음 회전할 지점은 우측상단을 기준으로 하여 r-i, c+i 로 회전을 시작할 지점을 설정

line 19) 하좌상우 방향으로 모두 밀어줘야하므로 4번 반복

line 20) 한 변에서 i*2만큼 이동해야한다.

line 21) 현재 좌표에서 해당 방향(하좌상우)으로 한 칸씩 이동

line 22) 이동한 좌표에 기존 좦표의 값을 저장

line 23) 현재 좌표를 다음 좌표로 저장(다음 좌표로 이동)

#. C++