[파이썬] 백준 17406 : 배열 돌리기 4 (골드4)

[파이썬] 백준 17406 : 배열 돌리기 4 (골드4)

17406번: 배열 돌리기 4

---

문제

---

풀이

0. 방향성 생각

• 순열로 모든 경우의 수 탐색
• 회전 시 중심좌표, 반지름을 받아서 회전시키기.
• 거리가 2 이상인 r인 경우에는 1~r까지 모두 회전시켜야함
• 원본 arr을 바꾸지 않도록 주의하기. 카피본 생성해야함
•  

1. 입력

from itertools import permutations as P
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w,t = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]

cmds = []
for _ in range(t):
    y,x,r = map(int,input().split())
    cmds.append((x-1,y-1,r))
per = list(P(cmds,len(cmds)))

• arr에 원본 받기
• cmds에 x좌표 y좌표 (인덱스는 0부터). 최대 반지름값 저장
• permutation에 모든 케이스 넣어주기

 

2. rotate 함수 정의

def rotate(x,y,r,array):
    temp = []
    
    temp.extend(array[y-r][x-r:x+r+1])
    for i in range(2*r-1):
        temp.append(array[y-r+1+i][x+r])
    temp.extend(array[y+r][x-r:x+r+1][::-1])
    for i in range(2*r-1):
        temp.append(array[y+r-1-i][x-r])
    temp = [temp[-1]] + temp[:-1]

    idx = 0
    for i in range(2*r):
        array[y-r][x-r+i] = temp[idx]
        idx += 1
    for i in range(2*r):
        array[y-r+i][x+r] = temp[idx]
        idx += 1
    for i in range(2*r):
        array[y+r][x+r-i] = temp[idx]
        idx += 1
    for i in range(2*r):
        array[y+r-i][x-r] = temp[idx]
        idx += 1
    return array

• temp에 회전시킬 모든 좌표를 받는다.
• 왼쪽 위부터 시계방향으로 모든 temp를 받고 마지막에 있는는 값을 temp의 맨 처음으로 이동
• temp를 왼쪽 위부터 채워넣는다

3. 출력

answer = []
for commands in per:

    arrc = [[val for val in row] for row in arr]
    
    for x,y,r in commands:
        for i in range(1,r+1):
            arrc = rotate(x,y,i,arrc)

    row_s = []
    for row in arrc:
        row_s.append(sum(row))
    answer.append(min(row_s))

print(min(answer))

• per에 있는 명령들을 commands로 받는다
• commands에 있는 명령들을 순차적으로 x,y,r로 받고
• r을 포함한 내부에 있는 배열들을 회전시킨다.
• 이후 row_sum에 합을 추가시킨다.
• answer에 각 케이스마다 최소값을 넣고 최종적으로 min(answer) 출력

---

전체코드

from itertools import permutations as P
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w,t = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]

cmds = []
for _ in range(t):
    y,x,r = map(int,input().split())
    cmds.append((x-1,y-1,r))
per = list(P(cmds,len(cmds)))


def rotate(x,y,r,array):
    temp = []
    
    temp.extend(array[y-r][x-r:x+r+1])
    for i in range(2*r-1):
        temp.append(array[y-r+1+i][x+r])
    temp.extend(array[y+r][x-r:x+r+1][::-1])
    for i in range(2*r-1):
        temp.append(array[y+r-1-i][x-r])
    temp = [temp[-1]] + temp[:-1]

    idx = 0
    for i in range(2*r):
        array[y-r][x-r+i] = temp[idx]
        idx += 1
    for i in range(2*r):
        array[y-r+i][x+r] = temp[idx]
        idx += 1
    for i in range(2*r):
        array[y+r][x+r-i] = temp[idx]
        idx += 1
    for i in range(2*r):
        array[y+r-i][x-r] = temp[idx]
        idx += 1
    return array


answer = []
for commands in per:

    arrc = [[val for val in row] for row in arr]
    
    for x,y,r in commands:
        for i in range(1,r+1):
            arrc = rotate(x,y,i,arrc)

    row_s = []
    for row in arrc:
        row_s.append(sum(row))
    answer.append(min(row_s))

print(min(answer))

 

코멘트

rotate(x,y,i,arrc)인데 i말고 r써놔서 진짜 억까당함