[백준 22949번] 회전미로(파이썬)

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

22949번: 회전 미로 탐색

 

문제를 보자마자

이게 뭐지??

하면서 당황했던 문제.

가장 문제에서 난감했던 부분은

'배열을 돌리고

해당 구역 이외에는 원상복귀시킨다'

구역이 계속 바뀐다고?

그러면 dfs로 풀어야하는거 아닌가?

구역을 계속 업데이트해주고...

하...이게 뭔 쌉소리지??

 

https://nahwasa.com/entry/%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-22949-%ED%9A%8C%EC%A0%84-%EB%AF%B8%EB%A1%9C-%ED%83%90%EC%83%89-java

[자바] 백준 22949 - 회전 미로 탐색 (java)

그렇게 질문게시판에 글을 올리고

어떤 왕고수님이 

'이거 이렇게 푸시면 됩니다'

하면서 블로그에 풀이를 올려놓으셨습니다.

이 분도 문제를 푸시면서

'어떻게 배열을 돌리지?'

에 대한 고민을 하셨습니다.

그러다가 이 분께서 주신 아이디어

'그럼 처음부터 미리 돌려주면 되잖아'

배열을 선언할 때 3차원으로 선언해주어서

[0]->안 돌릴때

[1]->한번 돌릴때

[2]->두 번 돌릴때

[3]->세번돌릴때

이렇콤 해주면 됩니다.

room=[[[0]*size for _ in range(size)] for _ in range(4)]

이렇게 room이라는 배열을 선언해주면 됩니다.

#미리 돌려준다
for x in range(size):
    for y in range(size):
        c=room[0][x][y]
        nx=x
        ny=y
        for d in range(1,4):
            gx,gy=get_rotate(nx,ny)
            room[d][gx][gy]=c
            nx,ny=gx,gy

 

그 다음으로 이렇게 돌려주면 

미리 돌려줄 때의 경우가 들어갑니다.

def get_rotate(x,y):
    baseX=x//4*4
    baseY=y//4*4
    x%=4
    y%=4

    return baseX+y,baseY+3-x

돌려주는 부분에 대한 함수.

제가 이 돌려주는 함수를 이해하지 못하고

한참을 해맸는데요.

이 문제에서 한 구역은

'4x4'입니다.

만약에 입력으로

4x4배열을 입력했다면

한 구역만 입력한 꼴.

저는 배열의 구역이

'배열의 크기를 기준으로

각각 1/4씩 나눈다'라고 잘못이해를 했습니다.

혼자 그렇게 삽질하다가

도움을 주신 분께

'저 좌표 돌아가는 거 함수 이상한데스요?'

하고 질문을 올리다가

'혹시 내가 잘못 이해했나?'

라면서 고수님께 질문드려보니

제가 잘못이해한 게 맞더군요.허허...

#백준 22949번 회전미로탐색
from collections import deque
k=int(input())

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


size=4*k
half=2*k
room=[[[0]*size for _ in range(size)] for _ in range(4)]
visited=[[[False]*size for _ in range(size)] for _ in range(4)]
fx=0
fy=0
def get_rotate(x,y):
    baseX=x//4*4
    baseY=y//4*4
    x%=4
    y%=4

    return baseX+y,baseY+3-x

def div(x,y):
    return x//4+y//4

for i in range(size):
    tmp=input().rstrip()
    for j in range(size):
        if tmp[j]=='S':
            fx=i
            fy=j
            room[0][i][j]=3
        elif tmp[j]=='.':
            room[0][i][j]=0

        elif tmp[j]=='#':
            room[0][i][j]=1

        elif tmp[j]=='E':
            room[0][i][j]=2

#미리 돌려준다
for x in range(size):
    for y in range(size):
        c=room[0][x][y]
        nx=x
        ny=y
        for d in range(1,4):
            gx,gy=get_rotate(nx,ny)
            room[d][gx][gy]=c
            nx,ny=gx,gy

answer=1e9
visited[0][fx][fy]=True

q=deque()
q.append([fx,fy,0,0])

while q:
    x,y,ro,cnt=q.popleft()

    if room[ro][x][y]==2:

        answer=min(answer,cnt)
        continue
    n_div=div(x,y)
    for d in range(5):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=size or ny<0 or ny>=size:
            continue
        #이동해서 다른 범위의 구역으로 가는지 아닌지 체크해준다
        #같은 범위면 돌려준다
        g_div=div(nx,ny)
        if n_div==g_div:
            nr=(ro+1)%4
        else:
            nr=1
        # print(nx,ny)
        n2x,n2y=get_rotate(nx,ny)
        # print(n2x, n2y)
        # print()
        if visited[nr][n2x][n2y]==True:
            continue
        if room[nr][n2x][n2y]==1:
            continue
        visited[nr][n2x][n2y]=True
        q.append([n2x,n2y,nr,cnt+1])

if answer==1e9:
    answer=-1
print(answer)

 

bfs문제중에서 상당히 어려웠던

그리고 발상자체가 참으로 신기했던 문제.

문제를 정리하면서 진짜

세상에 천재는 많다는 생각도.

+문제의 조건 꼼꼼히 읽자.