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

문제 설명

로봇개발자 “무지”는 한 달 앞으로 다가온 “카카오배 로봇경진대회”에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 “무지”는 “0”과 “1”로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 “0”은 빈칸을 “1”은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

“0”과 “1”로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

입출력 예

board	result
[[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]]	7

입출력 예 설명

문제에 주어진 예시와 같습니다. 로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

풀이과정

풀이 1

from collections import deque
def solution(board):
    n = len(board)-1
    answer = 0
    visited = set()
    
    
    # (0, 0), (0, 1)에서 시작
    visited.add(((0,0),(0,1)))
    visited.add(((0,1),(0,0)))
    
    q = deque()
    q.append(((0,0),(0,1),0))
    while q:
        
        s1, s2, cnt = q.popleft()
        
        if s1 == (n,n) or s2 == (n,n):
            return cnt
        
        x1, y1 = s1
        x2, y2 = s2
        
        de = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        
        # 평행 이동
        for d in de:
            dx, dy = d
            nx1, ny1 = x1+dx, y1+dy
            nx2, ny2 = x2+dx, y2+dy
            if 0 <= nx1 <= n and 0 <= ny1 <= n and 0 <= nx2 <= n and 0 <= ny2 <= n:
                if board[nx1][ny1] == 0 and board[nx2][ny2] == 0 and not ((nx1, ny1), (nx2, ny2)) in visited:
                    visited.add(((nx1, ny1), (nx2, ny2)))
                    visited.add(((nx2, ny2), (nx1, ny1)))
                    q.append(((nx1, ny1), (nx2, ny2), cnt+1))
        
        # 90도 회전
        if x1 == x2:
            for k in [-1, 1]:
                nx1 = x1 + k
                nx2 = x2 + k
                if 0 <= nx1 <= n and 0 <= nx2 <= n and board[nx1][y1] == 0 and board[nx2][y2] == 0:
                    if not ((nx1, y1), (x1, y1)) in visited:
                        visited.add(((nx1, y1), (x1, y1)))
                        visited.add(((x1, y1), (nx1, y1)))
                        q.append(((nx1, y1), (x1, y1), cnt + 1))
                    if not ((nx2, y2), (x2, y2)) in visited:
                        visited.add(((nx2, y2), (x2, y2)))
                        visited.add(((x2, y2), (nx2, y2)))
                        q.append(((nx2, y2), (x2, y2), cnt + 1))   
                
        if y1 == y2:
            for k in [-1, 1]:
                ny1 = y1 + k
                ny2 = y2 + k
                if 0 <= ny1 <= n and 0 <= ny2 <= n and board[x1][ny1] == 0 and board[x2][ny2] == 0:
                    if not ((x1, ny1), (x1, y1)) in visited:
                        visited.add(((x1, ny1), (x1, y1)))
                        visited.add(((x1, y1), (x1, ny1)))
                        q.append(((x1, ny1), (x1, y1), cnt + 1))
                    if not ((x2, ny2), (x2, y2)) in visited:
                        visited.add(((x2, ny2), (x2, y2)))
                        visited.add(((x2, y2), (x2, ny2)))
                        q.append(((x2, ny2), (x2, y2), cnt + 1))