블록 이동하기

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

📖 문제 해결
최단거리를 찾는 문제와 마찬가지로 bfs를 이용하여 문제를 풀되, 가로 혹은 세로로 이어진 형태로 2칸을 차지하는 로봇의 형태의 특수성과 로봇이 직선 이동만이 아닌 회전 이동을 할 수 있다는 점을 고려하여 코드를 구현한다면 문제를 해결할 수 있습니다. 이 해결 방법의 특징을 정리해 보면 다음과 같습니다.

(1) get_possible_pos 함수를 구현하여 다음으로 이동할 수 있는 위치를 찾음과 동시에 전체 코드를 간결화하였습니다.

(2) board를 변형한 리스트인 trans_board를 사용하여 인덱싱 가능 여부를 판단하는 코드를 사용하지 않을 수 있게 됨으로써 코드를 간결화할 수 있습니다.

(3) visited 리스트를 이용하여 방문하였던 위치는 다시 방문하지 않도록 함으로써 최단 거리를 계산할 수 있도록 하였습니다.

def get_possible_pos(pos,board):
    possible_pos = []
    
    pos = list(pos)
    pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    
    dx = [-1, +1, 0, 0]
    dy = [0, 0, -1, +1]
    
    # 직선 이동 고려
    for i in range(4):
        # 맵을 변형할 예정이므로 인덱싱 가능 여부는 검사하지 않아도 x
        if board[pos1_x + dx[i]][pos1_y + dy[i]] == 0 and board[pos2_x + dx[i]][pos2_y + dy[i]] == 0:
            possible_pos.append({(pos1_x + dx[i],pos1_y + dy[i]),(pos2_x + dx[i],pos2_y + dy[i])})

    
    # 회전 이동 고려
    # 로봇이 가로로 되어 있는 경우
    if pos1_x == pos2_x :
        for j in [-1, +1]:
            # 위쪽(혹은 아래쪽) 두 칸이 모두 비어있는 경우
            if board[pos1_x + j][pos1_y] == 0 and board[pos2_x + j][pos2_y] == 0:
                possible_pos.append({(pos1_x,pos1_y),(pos1_x + j,pos1_y)})
                possible_pos.append({(pos2_x,pos2_y),(pos2_x + j,pos2_y)})
                
    # 로봇이 세로로 되어 있는 경우
    if pos1_y == pos2_y :
        for j in [-1, +1]:
            # 위쪽(혹은 아래쪽) 두 칸이 모두 비어있는 경우
            if board[pos1_x][pos1_y + j] == 0 and board[pos2_x][pos2_y + j] == 0:
                possible_pos.append({(pos1_x,pos1_y),(pos1_x,pos1_y + j)})
                possible_pos.append({(pos2_x,pos2_y),(pos2_x,pos2_y + j)})
        
    return possible_pos
    
from collections import deque

def solution(board):
    
    n = len(board)
    
    # board을 변형
    trans_board = [[1]*(n+2) for _ in range(n+2)]
    
    for r_idx, row in enumerate(board):
        for c_idx, col in enumerate(row):
            trans_board[r_idx + 1][c_idx + 1] = board[r_idx][c_idx]
    
    pos = {(1,1),(1,2)}
    cost = 0
    
    # bfs를 이용하여 진행
    queue = deque()
    queue.append((pos, cost))
    visited = []
    
    while queue:
        pos, cost = queue.popleft()
        
        # 만약 도착 지점에 도달했다면 거리 반환
        if (n,n) in pos:
            return cost
        
        # 이동해가며 cost를 계산
        for pos_ in get_possible_pos(pos,trans_board):
            if pos_ not in visited:
                queue.append((pos_, cost+1))
                visited.append(pos_)
    
    return 0