[백준 25208번] 새벽의 탐정(파이썬)

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

25208번: 새벽의 탐정 게임

정육면체를 굴리면서 가야해서

체감난이도가 올라갔습니다.

도형굴리는 부분은

진짜 프로그래밍 삐긋~

해버리면 답이 안나오는 유형이라

돌리는 거 구현하는 것만으로도 스트레스받네요.

 

q에 cube를 받고

1을 바닥면으로 설정.

만약 x,y좌표에 도둑이 있고 cube[1]==1이라면

도둑을 잡은 것으로 설정.

이동하면서 조건에 맞게 cube를 돌려주면 됩니다.

 

#백준 25208번 새벽의 탐정게임
from heapq import heappop,heappush

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

N,M=map(int,input().split())
room=[[0]*M for _ in range(N)]
visited=[[[False]*7 for _ in range(M)] for _ in range(N)]
tmp=[list(input().rstrip()) for _ in range(N)]
sx,sy=-1,-1
ex,ey=-1,-1
for x in range(N):
    for y in range(M):
        if tmp[x][y]=='#':
            room[x][y]=1
        elif tmp[x][y]=='D':
            sx,sy=x,y
        elif tmp[x][y]=='R':
            ex,ey=x,y

q=[]
heappush(q,[0,sx,sy,[0,1,0,0,0,0,0]])
visited[sx][sy][1]=True
answer=1e9
while q:
    cnt,x,y,cube=heappop(q)
    if x==ex and y==ey:
        if cube[1]==1:
            answer=min(answer,cnt)
            continue
        else:
            continue

    for d in range(4):
        nx=x+dx[d]
        ny=y+dy[d]

        if nx<0 or nx>=N or ny<0 or ny>=M:
            continue

        if room[nx][ny]==1:
            continue
        #원래는 deepcopy를 써줬으나 시간초과 이슈가 생겨서
        #turn cube를 0000000으로 초기화하고
        #이전 cube에서 1인 부분만 index로 받아, 아직 돌리기전인 turn cube에 1을 넣어준다
        turn_cube=[0,0,0,0,0,0,0]
        n_b=cube.index(1)
        turn_cube[n_b]=1
        #방향에 따라 뒤집는다
        #상
        if d==0:
            turn_cube[1],turn_cube[4],turn_cube[6],turn_cube[5]=\
                turn_cube[5],turn_cube[1],turn_cube[4],turn_cube[6]
        #하
        elif d==1:
            turn_cube[1],turn_cube[4],turn_cube[6],turn_cube[5]=\
                turn_cube[4],turn_cube[6],turn_cube[5],turn_cube[1]
        #좌
        elif d==2:
            turn_cube[1],turn_cube[2],turn_cube[6],turn_cube[3]=\
                turn_cube[2],turn_cube[6],turn_cube[3],turn_cube[1]
        #우
        elif d==3:
            turn_cube[1],turn_cube[2],turn_cube[6],turn_cube[3]= \
                turn_cube[3], turn_cube[1], turn_cube[2], turn_cube[6]

        n_b=turn_cube.index(1)

        if visited[nx][ny][n_b]==True:
            continue

        visited[nx][ny][n_b]=True
        heappush(q,[cnt+1,nx,ny,turn_cube])

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

 

처음에는 deepcopy를 썼었는데

시간초과가 발생했습니다.

deepcopy가 시간을 많이 잡아먹는걸 알고있어서

위와 같이 코드를 수정했습니다.

정육면체 면 옮기는 부분을 공부하면서

bfs를 공부할 수 있는 좋은 문제입니다.