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

 

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

프로그래머스

---

📍 Problem

2x1 크기의 로봇이 좌표 (1, 1)에서 (N, N)까지 최소 비용으로 이동시킨다. 이동 조건은 다음과 같다.

1. 로봇은 앞 뒤 구분없이 움직일 수 있으며, 4방향으로 1칸씩 평행 이동이 가능하다.  한 칸 이동에 1초가 소요된다.
2. 4방향으로 90도 회전이 가능하며, 회전 방향에 벽이 없어야한다. 한번 회전에 1초가 소요된다.

---

💡 Solution

로봇의 현재 상태를 queue에 넣고 다음 가능한 이동을 체크하는 BFS 문제이다. 현재 로봇의 위치에 대해 가능한 이동 8가지 (4방향 평행이동, 4방향 회전)을 체크하고 가능하면 visited[로봇상태] 에 cost를 업데이트 시키면 된다. 문제 접근은 어렵지 않으나 회전 처리가  까다로운 문제이다.

 

회전 이동

1. 로봇이 세로 방향일 때와 가로 방향일 때 회전 처리가 다르다. 로봇의 방향은 로봇이 차지하는 두 칸이 x축이 동일한지(가로) y축이 동일한지(세로)로 판단한다. (is_robot_vertical())

2. 로봇은 각 축으로 왼쪽 회전, 오른쪽 회전이 가능하다.

로봇이 세로 방향이고, 좌우에 칸이 모두 0일 때 회전으로 가능한 이동은 다음과 같다. 

회전시 회전할 때 지나가는 칸과, 도착 칸에 벽이 없어야 한다. 예를 들어, (0, 0)을 축으로 오른쪽 회전과 (1, 0)을 축으로 오른쪽 회전은 같은 조건을 확인하게 된다. 

현재 상태 -> (0,0) 축 오른쪽 회전 / (1, 0) 축 오른쪽 회전

((0,0),(1,0)) 위치의 로봇의 오른쪽 두 칸((0, 0+1), (1, 0+1)) 에 벽이 없으면, 로봇은 ((0, 0), (0, 0+1)) 과 ((1, 0), (1, 0+1)) 로 이동할 수 있다.

따라서 세로 방향으로 있을 경우 현재 로봇의 좌표에서 (0, 1)와 (0, -1)  방향 이동된 좌표를 확인해 주면 된다. 코드로 나타내면 다음과 같다.  

a, b = ((0, 0), (1, 0)) # 현재 로봇이 차지하는 두 칸 a, b
cands = [] # 회전 가능한 위치
for dx, dy in [(0, 1), (0, -1)]: # 로봇이 세로 방향일 때 확인할 방향
    n_a = (a[0] + dx, a[1] + dy)
    n_b = (b[0] + dx, b[1] + dy)
    if board[n_a[0]][n_a[1]] == 0 and board[n_b[0]][n_b[1]] == 0: # 해당 위치의 벽 확인
        cands.append((a, n_a)) # 로봇의 회전 이동은, 한 칸은 위치가 유지된다. 
        cands.append((b, n_b))

 똑같이 가로 방향의 경우 (1, 0) 와 (-1, 0) 이동된 칸을 확인하면 된다. 추가적인 조건은 전체 코드를 참고한다. 

from collections import deque


directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]


def is_robot_vertical(robot):
    a, b = robot
    if a[0] == b[0]:
        return False
    return True


def can_move(board, robot):
    # 4방향 평행이동
    N = len(board)
    cands = []
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    a, b = robot
    for dx, dy in directions:
        n_a = (a[0] + dx, a[1] + dy)
        n_b = (b[0] + dx, b[1] + dy)
        if not 0 <= n_a[0] < N or not 0 <= n_a[1] < N:
            continue
        if not 0 <= n_b[0] < N or not 0 <= n_b[1] < N:
            continue
        if board[n_a[0]][n_a[1]] == 0 and board[n_b[0]][n_b[1]] == 0:
            cands.append((n_a, n_b))
    return cands


def can_rotate(board, robot):
    # 4방향 회전
    N = len(board)
    a, b = robot
    cands = []
    selected_dirs = []

    if is_robot_vertical(robot):
        selected_dirs += directions[:2]
    else:
        selected_dirs += directions[2:]

    for dx, dy in selected_dirs:
        n_a = (a[0] + dx, a[1] + dy)
        n_b = (b[0] + dx, b[1] + dy)
        if not 0 <= n_a[0] < N or not 0 <= n_a[1] < N:
            continue
        if not 0 <= n_b[0] < N or not 0 <= n_b[1] < N:
            continue
        if board[n_a[0]][n_a[1]] == 0 and board[n_b[0]][n_b[1]] == 0:
            cands.append((a, n_a))
            cands.append((b, n_b))
    return cands


def solution(board):
    N = len(board)
    visited = {}

    q = deque()
    initial_robot = ((0, 0), (0, 1))
    q.append(initial_robot)
    visited[initial_robot] = 0

    while len(q) > 0:
        node = q.popleft()
        if node[0] == (N-1, N-1) or node[1] == (N-1, N-1):
            return visited[node]

        for cand in can_move(board, node) + can_rotate(board, node):
            if cand in visited:
                continue
            q.append(cand)
            visited[cand] = visited[node] + 1


if __name__ == '__main__':
    board = [[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]]
    res = solution(board)
    print(res)

---