프로그래머스 블록 이동하기 (python, 파이썬)

• 문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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

---

• 코드

from collections import deque

def can_move(cur1, cur2, new_board):
    x, y = 0, 1
    cand = []
    
    # 평행이동
    dic = {0:[-1, 0], 1:[1, 0], 2:[0, 1], 3:[0, -1]}
    for i in range(4):
        nx1 = (cur1[x] + dic[i][0], cur1[y] + dic[i][1])
        nx2 = (cur2[x] + dic[i][0], cur2[y] + dic[i][1])
        if new_board[nx1[x]][nx1[y]] == 0 and new_board[nx2[x]][nx2[y]] == 0:
            cand.append((nx1, nx2))
            
    # 회전
    if cur1[x] == cur2[x]: # 가로방향 일 때
        UP, DOWN = -1, 1
        for d in [UP, DOWN]:
            if new_board[cur1[x]+d][cur1[y]] == 0 and new_board[cur2[x]+d][cur2[y]] == 0:
                cand.append((cur1, (cur1[x]+d, cur1[y])))
                cand.append((cur2, (cur2[x]+d, cur2[y])))
                
    else: # 세로 방향 일 때
        LEFT, RIGHT = -1, 1
        for d in [LEFT, RIGHT]:
            if new_board[cur1[x]][cur1[y]+d] == 0 and new_board[cur2[x]][cur2[y]+d] == 0:
                cand.append(((cur1[x], cur1[y]+d), cur1))
                cand.append(((cur2[x], cur2[y]+d), cur2))
                
    return cand

def solution(board):
    # board 외벽 둘러싸기
    n = len(board)
    new_board = [[1] * (n+2) for _ in range(n+2)]
    for i in range(n):
        for j in range(n):
            new_board[i+1][j+1] = board[i][j]
    
    for i in new_board:
        print(i)
        
    q = deque( [ ( (1, 1), (1, 2), 0 ) ] ) # 첫번쨰좌표 두번째좌표 시간
    check = set( [ ( (1, 1), (1, 2) ) ] )  # 방문확인용
    
    while q:
        cur1, cur2, time = q.popleft()
        if cur1 == (n, n) or cur2 == (n, n):
            return time
        
        for nxt in can_move(cur1, cur2, new_board):
            if nxt not in check:
                q.append((nxt[0], nxt[1], time+1))
                check.add(nxt)

---

• 출처

programmers.co.kr/learn/courses/30/lessons/60063?language=python3