블록 이동하기 (lv3)

문제 설명

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

---

 이 문제에서 중요한 포인트는 크게 세 가지 이다. 첫 번째는, 비용이 1로 고정된 특정 노드까지의 최단거리를 묻는 문제라는 점에서 BFS로 접근 가능하다는 것이다. 두 번째는, 이전까지 풀었던 BFS 최단거리 문제와 달리 단 한개의 노드에서 다른 노드로 이동하고 있지 않고 2 * 1 짜리 범위가 격자에서 한 칸씩 움직인다는 점이다. 따라서 노드 이동마다 1 씩 더하여 방문처리와 거리표시를 동시에 했던 방법은 쓸 수 없으며, 큐에 집어넣는 정보 역시 단 한개의 노드에 대한 열, 행 정보가 아니라 두개의 노드 정보를 넣어줘야 할 것이다. 회전, 이동 둘 다 1초로 비용이 고정되어 있으므로 반복문을 돌며 두 경우 모두 깊이 정보를 1 씩 갱신하면 될 것이다. 세 번째는, 이전 까지는 제한사항이 단순히 벽 혹은 격자 밖으로 나가는 것 정도로 주어졌지만, 이 문제에서는 회전할 때의 제한사항을 부가적으로 고려해줘야 한다는 것이다.

 

 가장 먼저 큰 틀을 잡는다. 기본적으로 다른 격자에서의 BFS 문제와 다를게 없다.

def get_rotation(loc):
    # 회전 했을 때 다음 위치를 반환함.
            
def bfs(loc,board):
    q = deque()
    # 큐에 넣어주는 정보는 위치와 비용.
    q.append((loc,0))
    while q:
        loc,cost = q.popleft()
        # 위치 집합에 목표 지점이 포함되어 있으면 종료.
        if (n,n) in loc:
            return cost
        # 움직이는 경우
        for i in range(4):
            # 네 방향을 돌아가며 다음 위치 정보 확보
            # 다음 위치 정보가 도달할 수 있는 위치인지 확인
        # 회전하는 경우
        for next_loc in get_rotation(loc):
            # 회전했을 때 다음 위치 후보들에 대해서 도달 가능한 위치인지 확인.

def solution(board):
    global n
    n = len(board[0])
    # 조금이라도 덜 복잡하게 하기 위해 보드 둘레에 1로 되어있는 벽을 만들어줌.
    for i in range(n):
        board[i] = [1,*board[i],1]
    board = [[1]*(n+2),*board,[1]*(n+2)]
    return bfs({(1,1),(1,2)},board)

 정의해준 get_rotation() 메서드를 구현할 차례이다. 물체가 가로로 놓여있을 때와 세로로 놓여있을 때가 조금 다른데, 일단 두 경우를 살펴보자.

 가로로 놓여있는 경우는 위 아래 좌표들을 받아 원래 위치 좌표들과 조합해주면 되고, 세로로 놓여있는 경우 양 옆에 대해서 해주면 된다. 이 때 주의해야할 점은 집합 자료형은 순서가 없기 때문에 정렬된 리스트로 받아온 후에 zip으로 묶어줘야 한다는 것이다.

rotate = {0:[(-1,0),(1,0)],1:[(0,-1),(0,1)]}

def get_rotation(loc):
	# 행끼리 값이 같은지, 열끼리 값이 같은지 확인하기 위해 zip으로 묶어준다.
    for i,v in enumerate(zip(*loc)):
        a,b = v
        if a-b == 0:
            targets = []
            for v in rotate[i]:
            	# rotate 딕셔너리에서 이동 정보를 가져와 합쳐준다.
                li = sorted(map(lambda x : tuple(sum(elem) for elem in zip(x,v)), loc))
                targets.append(li)
            # 이동 위치 좌표들과 원래 위치 좌표들을 조합해준다.
            return [set(elem) for target in targets for elem in zip(target,sorted(loc))]

 이제 마지막으로 BFS 를 구현해주면 되는데, 처음 설계할 때 발견한 것과 같이 물체가 회전할 때 중간에 벽이 있으면 안된다는 조건을 고려해야한다. 중간에 벽이 있으면 안된다, 라는 조건은, 이동하기 전과 이동한 후 좌표들이 만들 수 있는 2 * 2 크기의 정사각형에서 두 좌표 집합의 합집합을 빼주는 것으로 구현하였다.

코드

from collections import deque

n = -1
# 북,서,남,동
dRow = [-1,0,1,0]
dCol = [0,-1,0,1]

# 북,서,남,동
move = [(-1,0),(0,-1),(1,0),(0,1)]
# 회전 가로 세로
rotate = {0:[(-1,0),(1,0)],1:[(0,-1),(0,1)]}

visited = []

def get_rotation(loc):
    for i,v in enumerate(zip(*loc)):
        a,b = v
        if a-b == 0:
            targets = []
            for v in rotate[i]:
                li = sorted(map(lambda x : tuple(sum(elem) for elem in zip(x,v)), loc))
                targets.append(li)
            return [set(elem) for target in targets for elem in zip(target,sorted(loc))]
            
def bfs(loc,board):
    q = deque()
    q.append((loc,0))
    while q:
        loc,cost = q.popleft()
        if (n,n) in loc:
            return cost
        candidates = []
        # 움직이는 경우
        for i in range(4):
            next_loc = set(map(lambda x : tuple(sum(elem) for elem in zip(x,move[i])), loc))
            p1,p2 = next_loc
            nRow_1,nCol_1 = p1
            nRow_2,nCol_2 = p2
            if not next_loc in visited and board[nRow_1][nCol_1] == 0 and board[nRow_2][nCol_2] == 0:
                visited.append(next_loc)
                q.append((next_loc,cost+1))
        # 회전하는 경우
        for next_loc in get_rotation(loc):
            p1,p2 = next_loc
            nRow_1,nCol_1 = p1
            nRow_2,nCol_2 = p2
            if not next_loc in visited and board[nRow_1][nCol_1] == 0 and board[nRow_2][nCol_2] == 0:
                p = tuple(map(lambda x : max(x),zip(*(loc | next_loc))))
                pRow,pCol = p
                boundary = {(pRow-1,pCol-1),(pRow,pCol-1),(pRow-1,pCol),(pRow,pCol)}
                cRow,cCol = list(boundary - (loc | next_loc))[0]
                if board[cRow][cCol] == 0:
                    visited.append(next_loc)
                    q.append((next_loc,cost+1))

def solution(board):
    global n
    n = len(board[0])
    for i in range(n):
        board[i] = [1,*board[i],1]
    board = [[1]*(n+2),*board,[1]*(n+2)]
    return bfs({(1,1),(1,2)},board)