[백준 20327번] 배열 돌리기6(파이썬)

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

20327번: 배열 돌리기 6

 

 

문제 길이가 상당합니다.

이 문제에서 크게 생각할 건 2가지.

 

1. 어떻게 배열을 나누지?

2. 어떻게 연산하지?

 

저는 연산에 따라 나누는 걸 다르게 하는 쪽으로 접근했습니다.

연산은 부분이냐 배열이냐 2가지인데

이 연산에 따라서 나누는 방식이 달라져야겠다 생각했습니다.

# 배열 부분요소
if k<=4:
    if l==0:
        return
    else:
        #시작점 정하기
        for x in range(0,2**N,2**l):
            for y in range(0,2**N,2**l):
                #1번연산-->상하반전
                if k==1:
                    for a in range(2**(l-1)):
                        for b in range(2**l):
                            room[x+a][y+b],room[x+2**l-a-1][y+b]=room[x+2**l-a-1][y+b],room[x+a][y+b]

                #2번연산-->좌우반전
                elif k==2:
                    for b in range(2**(l-1)):
                        for a in range(2**l):
                            room[x+a][y+b],room[x+a][y+2**l-b-1]=room[x+a][y+2**l-b-1],room[x+a][y+b]

                #3번연산-->오른쪽 90
                elif k==3:
                    #먼저 임시로 배열을 받아준다.
                    tmp=[]
                    for a in range(2**l):
                        temp=[]
                        for b in range(2**l):
                            temp.append(room[x+a][y+b])
                        tmp.append(temp)
                    new=[[0]*2**l for _ in range(2**l)]
                    for a in range(2**l):
                        for b in range(2**l):
                            new[b][2**l-a-1]=tmp[a][b]

                    for a in range(2**l):
                        for b in range(2**l):
                            room[x+a][y+b]=new[a][b]


                #4번연산-->왼쪽 90
                elif k==4:
                    #먼저 임시로 배열을 받아준다.
                    tmp=[]
                    for a in range(2**l):
                        temp=[]
                        for b in range(2**l):
                            temp.append(room[x+a][y+b])
                        tmp.append(temp)
                    new=[[0]*2**l for _ in range(2**l)]
                    for a in range(2**l):
                        for b in range(2**l):
                            new[2**l-b-1][a]=tmp[a][b]

                    for a in range(2**l):
                        for b in range(2**l):
                            room[x+a][y+b]=new[a][b]

 

배열요소를 연산으로 구현한 부분입니다.

우선, 저는 시작점을 정했습니다.

배열요소를 연산해줄 때

각각 시작 포인트를 설정해주고

본격적으로 연산에 돌입했습니다.

1,2번은 상하/좌우 대칭이니

배열의 요소를 swap해주는 방식으로 접근했습니다.

3,4번은 배열을 90도만큼 돌려주는 방식인데

이걸 하려면 임시로 값을 받아야했습니다.

tmp라는 리스트에 연산할 배열을 받은 다음

90도 돌린 값을 new에 받았습니다.

그 뒤, new의 값을 room리스트에 반영하는 식으로 구현했습니다.

elif k>=5 and k<=8:
    #우선 배열을 먼저 받아보자
    ba=[]
    for x in range(0, 2 ** N, 2 ** l):
        temp=[]
        for y in range(0, 2 ** N, 2 ** l):
            tmp=[[0]*2**l for _ in range(2**l)]
            for a in range(2**l):
                for b in range(2**l):
                    tmp[a][b]=room[x+a][y+b]

            temp.append(tmp)
        ba.append(temp)
    ba_x=len(ba)
    ba_y=len(ba[0])

배열요소는 딱 보자마자 난감했습니다.

이건 배열 전체를 돌려야하는데...

그러다가 파이썬의 우수한 기술력으로

'각 배열을 리스트로 받아보자'라는 아이디어를 냈습니다.

그래서 ba라는 리스트를 만들고

l의 크기에 알맞게 배열들을 받았습니다.

이후 연산들은 1,2,3,4를 변형하면 되기 때문에

그렇게 어렵지 않았습니다.

#다 계산하고 넣어주기
for a in range(ba_x):
    for b in range(ba_y):

        now = ba[a][b]

        put_x = (2 ** l) * a
        start_y = (2 ** l) * b
        put_y = start_y
        p = 0

        for x in range(2 ** l):
            for y in range(2 ** l):
                put = now[x][y]
                room[put_x][put_y] = put
                put_y += 1
                p += 1
                if p == 2 ** l:
                    put_y = start_y
                    p = 0
                    put_x+=1

의외로 까다로운 건

room리스트에 반영하는 부분.

생각보다 값이 잘 안 넣어졌습니다.

저는 저런 식으로 put_x,put_y를 썼습니다.

1,2,3,4번을 구현했을 때

'시작점'이 있었다는 사실에 착안해서

저렇게 구현을 했습니다.

#백준 20327 배열돌리기 6
from copy import deepcopy
N,R=map(int,input().split())
room=[list(map(int,input().split()))for _ in range(2**N)]
dx=[0,1,0,-1]
dy=[1,0,-1,0]
dx2=[1,0,-1,0]
dy2=[0,1,0,-1]

do=[]
for _ in range(R):
    k,l=map(int,input().split())
    do.append([k,l])

#연산
#1 상하 반전 2 좌우반전 3오른쪽 90도 회전 4 왼쪽 90도 회전
#5 배열 상하반전 #6 배열 좌우반전 #7 배열 오른쪽 90도 #8 배열 90도 회전

def cal(k,l):
    global room
    # 배열 부분요소
    if k<=4:
        if l==0:
            return
        else:
            #시작점 정하기
            for x in range(0,2**N,2**l):
                for y in range(0,2**N,2**l):
                    #1번연산-->상하반전
                    if k==1:
                        for a in range(2**(l-1)):
                            for b in range(2**l):
                                room[x+a][y+b],room[x+2**l-a-1][y+b]=room[x+2**l-a-1][y+b],room[x+a][y+b]

                    #2번연산-->좌우반전
                    elif k==2:
                        for b in range(2**(l-1)):
                            for a in range(2**l):
                                room[x+a][y+b],room[x+a][y+2**l-b-1]=room[x+a][y+2**l-b-1],room[x+a][y+b]

                    #3번연산-->오른쪽 90
                    elif k==3:
                        #먼저 임시로 배열을 받아준다.
                        tmp=[]
                        for a in range(2**l):
                            temp=[]
                            for b in range(2**l):
                                temp.append(room[x+a][y+b])
                            tmp.append(temp)
                        new=[[0]*2**l for _ in range(2**l)]
                        for a in range(2**l):
                            for b in range(2**l):
                                new[b][2**l-a-1]=tmp[a][b]

                        for a in range(2**l):
                            for b in range(2**l):
                                room[x+a][y+b]=new[a][b]


                    #4번연산-->왼쪽 90
                    elif k==4:
                        #먼저 임시로 배열을 받아준다.
                        tmp=[]
                        for a in range(2**l):
                            temp=[]
                            for b in range(2**l):
                                temp.append(room[x+a][y+b])
                            tmp.append(temp)
                        new=[[0]*2**l for _ in range(2**l)]
                        for a in range(2**l):
                            for b in range(2**l):
                                new[2**l-b-1][a]=tmp[a][b]

                        for a in range(2**l):
                            for b in range(2**l):
                                room[x+a][y+b]=new[a][b]


    #배열전체
    elif k>=5 and k<=8:
        #우선 배열을 먼저 받아보자
        ba=[]
        for x in range(0, 2 ** N, 2 ** l):
            temp=[]
            for y in range(0, 2 ** N, 2 ** l):
                tmp=[[0]*2**l for _ in range(2**l)]
                for a in range(2**l):
                    for b in range(2**l):
                        tmp[a][b]=room[x+a][y+b]

                temp.append(tmp)
            ba.append(temp)
        ba_x=len(ba)
        ba_y=len(ba[0])


        #배열 상하반전
        if k==5:
            for a in range(ba_x//2):
                for b in range(ba_y):
                    ba[a][b],ba[ba_x-a-1][b]=ba[ba_x-a-1][b],ba[a][b]


        #배열 좌우반전
        elif k==6:
            for b in range(ba_y//2):
                for a in range(ba_x):
                    ba[a][b],ba[a][ba_y-b-1]=ba[a][ba_y-b-1],ba[a][b]
        #배열 오른쪽 90도 회전
        elif k==7:
            new=deepcopy(ba)
            for a in range(ba_x):
                for b in range(ba_y):
                    new[b][ba_x-a-1]=ba[a][b]
            ba=new

        #베열 왼쪽 90도 회전
        elif k==8:
            new=deepcopy(ba)
            for a in range(ba_x):
                for b in range(ba_y):
                    new[ba_y-b-1][a]=ba[a][b]
            ba=new

        #다 계산하고 넣어주기
        for a in range(ba_x):
            for b in range(ba_y):

                now = ba[a][b]

                put_x = (2 ** l) * a
                start_y = (2 ** l) * b
                put_y = start_y
                p = 0

                for x in range(2 ** l):
                    for y in range(2 ** l):
                        put = now[x][y]
                        room[put_x][put_y] = put
                        put_y += 1
                        p += 1
                        if p == 2 ** l:
                            put_y = start_y
                            p = 0
                            put_x+=1


for i in range(R):
    k,l=do[i]
    cal(k,l)

for i in range(2**N):
    for j in range(2**N):
        print(room[i][j],end=' ')
    print()

 

문제의 체감난이도가 높고

리스트에 대한 활용을 물어보는 것이라

한번쯤 봐보면 좋을 문제입니다.