[카카오] 블록 이동하기 ( 파이썬 )

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

문제 풀이

• visited는 딕셔너리로 선언해서 키 값에 sx,sy,ex,ey 방문한 것들을 넣어주고 최소로 도착하는 시간을 기록해둠
• 동,서,남,북으로 이동했을 시에는 sx,sy,ex,ey의 순서는 그대로 유지된다.
• 90도로 꺽을 시에 생기는 유의 사항들
  • 도형이 누워있거나 세워져 있거나에 따라 변하는 점이 달라짐. 
  • 90도로 꺽을 때 위에 있는, 왼쪽에 있는 점이 sx,sy가 되므로 좌표 계산 후 이 점을 유의해서 sx,syex,ey를 재조정
  • 꺽을 때 기준점과 변하는 점 사이의 있는 점이 벽인지 체크 해줘야 함
• 위의 유의사항들은 그림으로 그려보고 찾아봄. 세번째 사항인 사이에 있는 점을 체크하는 것도 좌표 계산 리스트에 같이 넣어서 후에 for문에서 계산하게 함

소스 코드

from collections import deque

dir = [
        [-1,0,-1,0],
        [1,0,1,0],
        [0,-1,0,-1],
        [0,1,0,1],
        ]	#동서남북

	#rot[0]은 도형이 누워있을때 변하는 점들. 
    #rot[1]은 세워져 있을때 
   	#각 요소 [4]~[7]은 사이에 있는 점이 벽인지 체크 하기 위해 넣어준 것들
rot = [[[0,0,-1,-1,0,0,-1,0],[0,0,1,-1,0,0,1,0],[-1,1,0,0,-1,0,0,0],[1,1,0,0,1,0,0,0]],  [[0,0,-1,-1,0,0,0,-1],[0,0,-1,1,0,0,0,1],[1,-1,0,0,0,-1,0,0],[1,1,0,0,0,1,0,0]]]

def solution(gr):
    n = len(gr)
    visited = {}
    visited[0,0,0,1] = 0
    q= deque()
    q.append((0,0,0,1,0,0))
    answer = int(1e9)
    while(q):
        sx,sy,ex,ey,dic,d = q.popleft() # dic => 0 가로, 1 세로
        if [sx,sy]==[n-1,n-1] or [ex,ey]==[n-1,n-1]:
            answer = min(d,answer)
            continue
        for i in range(8):
            if i<4:
                nsx,nsy,nex,ney = sx+dir[i][0],sy+dir[i][1],ex+dir[i][2],ey+dir[i][3]
                if nsx<0 or nsy<0 or nex<0 or ney<0 or nsx>=n or nex>=n or nsy>=n or ney>=n:
                    continue
                `if gr[nsx][nsy]==1 or gr[nex][ney]==1:
                    continue
                if (nsx,nsy,nex,ney) not in visited or visited[nsx,nsy,nex,ney]>d+1:
                    visited[nsx,nsy,nex,ney] = d+1
                    q.append((nsx,nsy,nex,ney,dic,d+1))
                    
            else:
                j=i-4
                nsx,nsy,nex,ney = sx+rot[dic][j][0],sy+rot[dic][j][1],ex+rot[dic][j][2],ey+rot[dic][j][3]
                csx,csy,cex,cey = sx+rot[dic][j][4],sy+rot[dic][j][5],ex+rot[dic][j][6],ey+rot[dic][j][7]
                if nsx<0 or nsy<0 or nex<0 or ney<0 or nsx>=n or nex>=n or nsy>=n or ney>=n:
                    continue
                if gr[nsx][nsy]==1 or gr[nex][ney]==1 or gr[csx][csy]==1 or gr[cex][cey]==1:
                    continue
                ddd = 1 if dic==0 else 0
                if j in [0,3]:		# 변한 ex,ey가 원점에 더 가까워서 sx,sy가 되는 경우들임
                    if ((nex,ney,nsx,nsy) not in visited or visited[nex,ney,nsx,nsy]>d+1) :
                        visited[nex,ney,nsx,nsy] = d +1    
                        q.append((nex,ney,nsx,nsy,ddd,d+1))
                else:
                    if ((nsx,nsy,nex,ney) not in visited or visited[nsx,nsy,nex,ney]>d+1):
                        visited[nsx,nsy,nex,ney] = d +1    
                        q.append((nsx,nsy,nex,ney,ddd,d+1))        

                        
    return answer

print(solution([[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]))