프로그래머스 블록 이동하기 파이썬

문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

입출력 예

boardresult

[[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초가 걸립니다.

 

문제풀이

로봇은 길이가 2고, 어떤 축으로든 회전이 가능하다고 한다. 회전이 가능하기 때문에, 회전된 상태가 무엇인지에 따라 방문하는 시간이 다를 수 있다. 따라서 가로로 도착했을 때의 최소 시간, 세로로 도착했을 때의 최소 시간을 따로 기록해야한다.

로봇의 길이가 2이기 때문에 로봇 좌표를 a,b 2개로 관리했다. 이 이유 때문에 추가로 방문할 것을 고려할 때, 방문하고자 하는 두 점의 위치 중 하나라도 현재 시간이 최소가 되면 다시 한번 더 방문을 해야할 필요가 있다. 그래서 추가로 더 방문해야하는지를 결정하는 방법을 위와 같이 설정했다. 

또 다른 중요 포인트는 로봇의 회전이었다. 로봇이 회전하게 되면, 이게 정말 회전이 가능한지를 살펴봐야했다. 이것은 아래 그림을 바탕으로 판별했다. 

a가 b의 아래로 회전을 했다면, 아래의 두 조건을 만족해야한다.

1. a가 b아래로 회전할 때, 벽이 없어야 한다.
   즉, 기존 a의 위치에서 열만 변했을 때, 행만 변했을 때 각각에서 벽이 없어야 한다.
2. a의 열이 b의 열과 일치해야한다.
   제대로 회전을 했다면, 반드시 열 혹은 행이 하나가 일치해야한다. 그렇지 않으면 a의 좌표가 이상한 방향으로 날아가버릴 수 있다.

 

위에서 설명한 것들을 감안해서 BFS로 최소 방문 시간을 확인한 코드를 아래에 작성했다. 

from collections import deque
def bfs(board) :

    # 초기 변수 셋팅
    n = len(board)
    que = deque()
    v = [[[9876543210 for _ in range(n)] for _ in range(n)] for _ in range(2)]

    #시작점 방문처리.
    que.append((0,0,0,1,0,0))
    v[0][0][0] = 0
    v[0][0][1] = 0



    while que :
        #ar,ac = 점 a의 좌표
        #br,bc = 점 b의 좌표
        #status = 현재 로봇이 놓여있는 상태(0은 가로, 1은 세로)
        ar, ac, br, bc, now_time, status = que.popleft()


        #목적지 도착했는지 판단
        if (ar == n-1 and ac == n -1) or (br == n-1 and bc == n-1) :
             return now_time
        if br == n-1 and bc == n-1 :
            return now_time

        next_time = now_time + 1

        #회전하지 않고 그대로 가는 경우
        for rr, cc in tra_list :
            next_ar = ar + rr
            next_ac = ac + cc
            next_br = br + rr
            next_bc = bc + cc
            next_status = status
            if -1 < next_ar < n and -1 < next_br < n and -1 <  next_ac < n and -1 < next_bc < n :
                if board[next_ar][next_ac] == 0 and board[next_br][next_bc] == 0 :
                    if v[next_status][next_ar][next_ac] > next_time or v[next_status][next_br][next_bc] > next_time :
                        que.append((next_ar, next_ac, next_br, next_bc, next_time, next_status))
                        v[next_status][next_ar][next_ac] = min(next_time, v[next_status][next_ar][next_ac])
                        v[next_status][next_br][next_bc] = min(next_time, v[next_status][next_br][next_bc])


        if status == 1 :
            next_status = 0
        else :
            next_status = 1

        # a를 중심축으로 회전해서 가는 경우
        for rr, cc, in rotate :
            next_ar = ar + rr
            next_ac = ac + cc
            if -1 < next_ar < n and -1 < next_ac < n:
                # 회전하는 곳에서 벽이 있을 때, 뒤로 안감
                if board[next_ar][ac] == 1 or board[ar][next_ac] == 1 :
                    continue
                # 회전이 정상적으로 이루어 졌을 때
                if next_ar == br or next_ac == bc:
                    if board[next_ar][next_ac] == 0 and board[br][bc] == 0 :
                        if v[next_status][next_ar][next_ac] > next_time or v[next_status][br][bc] > next_time :
                            que.append((next_ar, next_ac, br, bc, next_time, next_status))
                            v[next_status][next_ar][next_ac] = min(next_time, v[next_status][next_ar][next_ac])
                            v[next_status][br][bc] = min(next_time, v[next_status][br][bc])


        # b를 중심축으로 회전해서 가는 경우
        for rr, cc, in rotate :
            next_br = br + rr
            next_bc = bc + cc
            if -1 < next_br < n and -1 < next_bc < n:

                # 회전하는 곳에서 벽이 있을 때, 뒤로 안감
                if board[next_br][bc] == 1 or board[br][next_bc] == 1 :
                    continue
                # 회전이 정상적으로 이루어 졌을 때
                if next_br == ar or next_bc == ac :
                    if board[next_br][next_bc] == 0 and board[ar][ac] == 0 :
                        if v[next_status][next_br][next_bc] > next_time or v[next_status][ar][ac] > next_time :
                            que.append((ar, ac, next_br, next_bc, next_time, next_status))
                            v[next_status][ar][ac] = min(next_time, v[next_status][ar][ac])
                            v[next_status][next_br][next_bc] = min(next_time,v[next_status][next_br][next_bc])





tra_list = [[1,0],[0,1],[-1,0],[0,-1]]
rotate = [[1,1], [1,-1],[-1,1],[-1,-1]]


def solution(board):
    answer = bfs(board)
    return answer