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

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

17406번: 배열 돌리기 4

구현해줘야할 부분은 2가지.

 

1. 배열 돌리기

 

2. 배열 돌리는 거 백트레킹

 

구현할 2가지가 난이도가 상당히 있는 편이라

체감난이도가 높았던 문제입니다.

우선 배열을 돌리는 것부터 차근히 보겠습니다.

def rotate(r,c,s):
    #s의 수만큼 돌린다
    for ro in range(s,0,-1):
        s_x=r-ro
        s_y=c-ro
        #돌리는 횟수는 ro*8
        p=0
        r_d=0
        r_m=0
        tmp=A[s_x][s_y]
        go_x=s_x
        go_y=s_y
        while p<ro*8:
            #돌리기
            if r_d==0:
                move_x=go_x
                move_y=go_y+1
            elif r_d==1:
                move_x=go_x+1
                move_y=go_y
            elif r_d==2:
                move_x=go_x
                move_y=go_y-1
            elif r_d==3:
                move_x=go_x-1
                move_y=go_y

            if r_m>=ro*2:
                r_d=(r_d+1)%4
                r_m=0
                continue

            go_x=move_x
            go_y=move_y
            #값 넘겨주기
            tmp2=A[go_x][go_y]
            A[go_x][go_y]=tmp
            tmp=tmp2


            p+=1
            r_m+=1

 

직접 노트에 그려넣으면서

어떻게 배열이 돌아갈까 보면서 작성했습니다.

큰 거 부터 돌리니깐

ro는 s의 역순으로 구현했습니다.

돌리는 횟수는 직접 세어보면서 발견해보니

ro*8이었습니다.

돌리는 건 상하좌우 나눠서

r_d의 숫자대로 순서대로

우 하 좌 상 이렇게 구현했습니다.

r_d는 r_m이 ro*2 이상일 때 초기화시키고

r_d의 1을 더하는 식으로 했습니다.

r_d는 상하좌우 각각 최대 몇 번 움직이는 지에 대한 값이라

이렇게 구현해줘야 원하는 데로 이동이 가능했습니다.

그 다음에는 값을 넘겨줬습니다.

 

def sol(n):
    global answer
    global A
    if n==K:
        ma=[0]*N
        for i in range(N):
            ma[i]=sum(A[i])
        tmp=min(ma)
        answer=min(answer,tmp)
        return

    else:
        for i in range(K):
            if visited[i]==False:
                t_A=deepcopy(A)
                visited[i]=True
                r,c,s=rot[i]
                rotate(r,c,s)
                sol(n+1)
                visited[i]=False
                A=deepcopy(t_A)

 

백트레킹하는 과정입니다.

우선, visited=[False]*K를 생성해줍니다.

for문을 돌리다가

false를 만나면 

rot(돌리는 것을 여기 리스트에 저장했습니다)에서

rot[i]를 불러오고 돌려줍니다.

그 다음 n+1해서 sol를 재귀적으로 실행해주고요.

sol이 K만큼 찼으면

배열의 값을 보고 최솟값인지 구하면 됩니다.

백트레킹에서 중요한 부분은

'다시 되돌리기'입니다.

저는 이 부분을 deepcopy로 구현했습니다.

deepcopy로 돌리전 배열을 저장해두고

return후 다른 걸 시행할 때

deepcopy했던 배열을 복사해줍니다.

#백준 17406번 배열돌리기
from copy import deepcopy

N,M,K=map(int,input().split())
A=[list(map(int,input().split()))for _ in range(N)]
rot=[]
visited=[False]*K
answer=1e9

for _ in range(K):
    r,c,s=map(int,input().split())
    rot.append([r-1,c-1,s])
#배열돌리기 먼저
def rotate(r,c,s):
    #s의 수만큼 돌린다
    for ro in range(s,0,-1):
        s_x=r-ro
        s_y=c-ro
        #돌리는 횟수는 ro*8
        p=0
        r_d=0
        r_m=0
        tmp=A[s_x][s_y]
        go_x=s_x
        go_y=s_y
        while p<ro*8:
            #돌리기
            if r_d==0:
                move_x=go_x
                move_y=go_y+1
            elif r_d==1:
                move_x=go_x+1
                move_y=go_y
            elif r_d==2:
                move_x=go_x
                move_y=go_y-1
            elif r_d==3:
                move_x=go_x-1
                move_y=go_y

            if r_m>=ro*2:
                r_d=(r_d+1)%4
                r_m=0
                continue

            go_x=move_x
            go_y=move_y
            #값 넘겨주기
            tmp2=A[go_x][go_y]
            A[go_x][go_y]=tmp
            tmp=tmp2


            p+=1
            r_m+=1


def sol(n):
    global answer
    global A
    if n==K:
        ma=[0]*N
        for i in range(N):
            ma[i]=sum(A[i])
        tmp=min(ma)
        answer=min(answer,tmp)
        return

    else:
        for i in range(K):
            if visited[i]==False:
                t_A=deepcopy(A)
                visited[i]=True
                r,c,s=rot[i]
                rotate(r,c,s)
                sol(n+1)
                visited[i]=False
                A=deepcopy(t_A)



sol(0)
print(answer)

pypy3로 제출한 코드입니다.

https://dev-dain.tistory.com/154

[백준] 17406 : 배열 돌리기 4 (Python3)

https://chldkato.tistory.com/137

백준 17406 배열 돌리기 4 (파이썬)

배열을 돌리는 방식이

저랑은 다르게 하신 분들이 많네요.

이것저것 보면서 공부해야겠네요.