(python)프로그래머스-블록 이동하기

문제

2x1 크기의 로봇이 이동해서 (n,n) 도달하기까지의 최소시간을 구하는 문제이다.

로봇의 움직임의 모든 경우를 고려해서 이동할수있는 좌표를 구하고 bfs로 최소 시간을 구하는 문제이다.

로봇 움직임을 구하는데 오래걸렸다,,ㅠㅠ

from collections import deque
def find_next(q,board):
    next_pos=[]
    q=list(q)
    x1,y1,x2,y2=q[0][0],q[0][1],q[1][0],q[1][1]
    #상하좌우로 움직일 경우
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    for i in range(4):
        n_x1,n_y1,n_x2,n_y2=x1+dx[i],y1+dy[i],x2+dx[i],y2+dy[i]
        if board[n_x1][n_y1]==0 and board[n_x2][n_y2]==0:
            next_pos.append({(n_x1,n_y1),(n_x2,n_y2)})
    #로봇이 가로로 놓여있을 경우 
    if x1==x2:
        #위쪽 혹은 아래쪽 회전할 경우 2가지
        for i in [1,-1]:
            if board[x1+i][y1]==0 and board[x2+i][y2]==0:
                next_pos.append({(x1,y1),(x1+i,y1)})
                next_pos.append({(x2,y2),(x2+i,y2)})
    #로봇이 세로로 놓여있을 경우
    elif y1==y2:
        #왼쪽 혹은 오른쪽으로 회전할 경우 2가지
        for i in [1,-1]:
            if board[x1][y1+i]==0 and board[x2][y2+i]==0:
                next_pos.append({(x1,y1),(x1,y1+i)})
                next_pos.append({(x2,y2),(x2,y2+i)})
    return next_pos

def solution(board):
    n=len(board)
    #board의 테두리를 1로 감싸기
    new_board=[[1]*(n+2) for i in range(n+2)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            new_board[i][j]=board[i-1][j-1]
    
    #현재좌표
    pos={(1,1),(1,2)}
    #방문 배열
    visited=[]
    #초기 값 queue에 삽입 초기 걸린시간=0
    queue=deque()
    queue.append((pos,0))
    #방문 기록하기
    visited.append(pos)
    #queue가 빌때까지,bfs
    while queue:
        n_pos,n_cost=queue.popleft()
        if (n,n) in n_pos:
            answer=n_cost
            break
        for next_pos in find_next(n_pos,new_board):
            if next_pos not in visited:
                visited.append(next_pos)
                queue.append((next_pos,n_cost+1))
    return answer