[프로그래머스] 블록 이동하기 (Python)

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

코딩테스트 연습 - 블록 이동하기

힘든 구현 문제다. 이게 맞나 싶으면서 그냥 구현했다.

bfs로 풀었다.

 

나의 풀이

from collections import deque,defaultdict
def solution(board):
    length = len(board)
    visited = defaultdict(int)
    visited[(0,0,0,1)] = 1
    q = deque([(0,0,0,1,0)])
    while q:
        x, y, i, j, answer = q.popleft()
        if (x == length-1 and y ==length-1) or (i ==length-1 and j ==length-1):
            return answer
        robot = 1 if x == i else 0
        if robot:
            #가로 상태
            if j != length-1: # 끝점이 아닐 때
                # 우로이동
                if board[i][j+1] != 1 and visited[(x,y+1,i,j+1)] != 1:
                    # if i == length -1 and j+1 == length -1:
                    #     return answer+1
                    visited[(x,y+1,i,j+1)] = 1
                    q.append((x,y+1,i,j+1,answer+1))
            if y != 0: # 끝점이 아닐 때
                # 좌로이동
                if board[x][y-1] != 1 and visited[(x,y-1,i,j-1)] != 1:
                    visited[(x,y-1,i,j-1)] = 1
                    q.append((x,y-1,i,j-1,answer+1))
            if x != length -1: # 끝점이 아닐 때
                # 아래로
                if board[x+1][y] != 1 and board[i+1][j] != 1 and visited[(x+1,y,i+1,j)] != 1:
                    visited[(x+1,y,i+1,j)] = 1
                    q.append((x+1,y,i+1,j,answer+1))
            if x != 0: # 끝점이 아닐 때
                # 위로
                if board[x-1][y] != 1 and board[i-1][j] != 1 and visited[(x-1,y,i-1,j)] != 1:
                    visited[(x-1,y,i-1,j)] = 1
                    q.append((x-1,y,i-1,j,answer+1))
            if x != length-1: # 끝점이 아닐 때
                # a를 축으로 아래로 회전
                if board[x+1][y+1] !=1 and board[x+1][y] !=1 and visited[(x,y,x+1,y)] !=1:
                    visited[(x,y,x+1,y)] = 1
                    q.append((x,y,x+1,y,answer+1))
            if x != 0: # 끝점이 아닐 때
                # a를 축으로 위로 회전
                if board[x-1][y+1] !=1 and board[x-1][y] !=1 and visited[(x-1,y,x,y)] !=1:
                    visited[(x-1,y,x,y)] = 1
                    q.append((x-1,y,x,y,answer+1))
            if i != length-1: # 끝점이 아닐 때
                # b를 축으로 아래로 회전
                if board[i+1][j-1] != 1 and board[i+1][j] !=1 and visited[(i,j,i+1,j)] !=1:
                    if i+1 == length-1 and j == length-1:
                        return answer+1
                    visited[(i,j,i+1,j)] = 1
                    q.append((i,j,i+1,j,answer+1))
            if i != 0: # 끝점이 아닐 때
                # b를 축으로 위로 회전
                if board[i-1][j-1] !=1 and board[i-1][j] !=1 and visited[(i-1,j,i,j)] !=1:
                    visited[(i-1,j,i,j)] = 1
                    q.append((i-1,j,i,j,answer+1))
        else:
            if x != 0: # 끝점이 아닐 때
                # 위로 이동
                if board[x-1][y] != 1 and visited[(x-1,y,x,y)] != 1:
                    visited[(x-1,y,x,y)] = 1
                    q.append((x-1,y,x,y,answer+1))
            if i != length-1: # 끝점이 아닐 때
                # 아래로 이동
                if board[i+1][j] != 1 and visited[(i,j,i+1,j)] != 1:
                    # if i+1 == length-1 and j == length-1:
                    #     return answer+1
                    visited[(i,j,i+1,j)] = 1
                    q.append((i,j,i+1,j,answer+1))
            if y != length -1: # 끝점이 아닐 때
                # 우로
                if board[x][y+1] != 1 and board[i][j+1] != 1 and visited[(x,y+1,i,j+1)] != 1:
                    visited[(x,y+1,i,j+1)] = 1
                    q.append((x,y+1,i,j+1,answer+1))
            if y != 0: # 끝점이 아닐 때
                # 좌로
                if board[x][y-1] != 1 and board[i][j-1] != 1 and visited[(x,y-1,i,j-1)] != 1:
                    visited[(x,y-1,i,j-1)] = 1
                    q.append((x,y-1,i,j-1,answer+1))
            if y != 0: # 끝점이 아닐 때
                # a를 축으로 좌로 회전
                if board[x+1][y-1] !=1 and board[x][y-1] !=1 and visited[(x,y-1,x,y)] !=1:
                    visited[(x,y-1,x,y)] = 1
                    q.append((x,y-1,x,y,answer+1))
            if y != length-1: # 끝점이 아닐 때
                # a를 축으로 우로 회전
                if board[x+1][y+1] !=1 and board[x][y+1] !=1 and visited[(x,y,x,y+1)] !=1:
                    visited[(x,y,x,y+1)] = 1
                    q.append((x,y,x,y+1,answer+1))
            if j != 0: # 끝점이 아닐 때
                # b를 축으로 좌로 회전
                if board[i-1][j-1] != 1 and board[i][j-1] !=1 and visited[(i,j-1,i,j)] !=1:
                    visited[(i,j-1,i,j)] = 1
                    q.append((i,j-1,i,j,answer+1))
            if j != length-1: # 끝점이 아닐 때
                # b를 축으로 우로 회전
                if board[i-1][j+1] !=1 and board[i][j+1] !=1 and visited[(i,j,i,j+1)] !=1:
                    # if i == length-1 and j+1 == length-1:
                    #     return answer+1
                    visited[(i,j,i,j+1)] = 1
                    q.append((i,j,i,j+1,answer+1))