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

bfs를 이용하여 해결했습니다.

bfs에 들어가는 값으로는 [[로봇위치1, 로봇위치2], 시간] 이 들어갑니다.

그리고 위치1의 값은 위치2보다 항상 작습니다.

[[0,0],[0,1]]

[[0,0],[1,0]]

 

문제는 다음에 방문할 위치에 대한 정보입니다.

 

회전에 대해서는 정사각형을 만들어서 처리했습니다.

만약 이 사각형에 1이 있다면 회전을 하지 못한다는 것을 의미합니다.

1이 없고 회전시킨 위치를 방문하지 않았다면, 큐에 (현재 시간+1)과 회전시킨 위치를 넣어줍니다. 

 

방문했는 지 확인하기 위해서 set을 이용했습니다. 문제는 list는 set에 들어갈 수 없기 때문에 tuple로 바꿔서 넣었습니다.

 

상하좌우는 일반적인 bfs문제와 동일하게 처리했습니다.

 

큐에서 꺼낸 위치에서 보드의 맨 마지막 위치가 있을 경우에는 현재 시간을 return 해줍니다.

 

from collections import deque

def solution(board):
    return bfs(board)


def is_out(y1,x1,y2,x2, n):
    if y1 < 0 or y1 >= n or y2 < 0 or y2 >= n or x1 < 0 or x1 >= n or x2 < 0 or x2 >= n:
        return True
    return False


def bfs(board):    
    vertical_squares = [[0,-1], [0,1]]
    horizontal_squares = [[-1,0], [1,0]]
    
    visited = set()
    
    q =deque()
    q.append([((0,0), (0,1)),0])
    
    visited.add(((0,0), (0,1)))
    
    while q:
        p,t= q.popleft()
        print(p,t)
        for y,x in p:
            if y==len(board)-1 and x == len(board)-1:
                return t
        
        #가로
        if p[0][0] == p[1][0]:
            for dy, dx in horizontal_squares:
                ny1, nx1, ny2, nx2 = p[0][0]+dy, p[0][1]+dx, p[1][0]+dy, p[1][1]+dx
                
                if is_out(ny1,nx2,ny2,nx2,len(board)):
                    continue
                    
                if board[ny1][nx1] == 1 or board[ny2][nx2] == 1:
                    continue
                
                npos = [[ny1, nx1], [ny2, nx2]]
                
                for i in range(2):
                    robot_pos = [[p[i][0], p[i][1]], [npos[i][0] ,  npos[i][1]]]
                    robot_pos.sort(key= lambda x : (x[0], x[1]))
                    
                    robot_pos = (tuple(robot_pos[0]), tuple(robot_pos[1]))
                    if robot_pos in visited:
                        continue
                    
                    visited.add(robot_pos)
                    q.append([robot_pos, t+1])
        #세로
        else:
            for dy, dx in vertical_squares:
                ny1, nx1, ny2, nx2 = p[0][0]+dy, p[0][1]+dx, p[1][0]+dy, p[1][1]+dx
                
                if is_out(ny1,nx2,ny2,nx2,len(board)):
                    continue
                    
                if board[ny1][nx1] == 1 or board[ny2][nx2] == 1:
                    continue
                
                npos = [[ny1, nx1], [ny2, nx2]]
                
                for i in range(2):
                    robot_pos = [[p[i][0], p[i][1]], [npos[i][0] , npos[i][1]]]
                    robot_pos.sort(key= lambda x : (x[0], x[1]))
                    
                    robot_pos = (tuple(robot_pos[0]), tuple(robot_pos[1]))
                    if robot_pos in visited:
                        continue
                    
                    visited.add(robot_pos)
                    q.append([robot_pos, t+1])
          
        direction = [[1,0],[0,1],[-1,0],[0,-1]]
        
        # 이동
        for dy, dx in direction:
            robot_pos = ((p[0][0]+dy, p[0][1]+dx),(p[1][0]+dy,p[1][1]+dx))
            
            if is_out(robot_pos[0][0], robot_pos[0][1], robot_pos[1][0], robot_pos[1][1], len(board)):
                continue
            if board[robot_pos[0][0]][robot_pos[0][1]] == 1 or board[robot_pos[1][0]][robot_pos[1][1]] == 1:
                    continue
        
            if robot_pos in visited:
                continue
            
            visited.add(robot_pos)
            q.append([robot_pos, t+1])

코드는 매우 지저분합니다.