[DFS/BFS] Q22 블록 이동하기

난이도: 3 / 풀이 시간: 50분
link: https://school.programmers.co.kr/learn/courses/30/lessons/60063

주의! 이 문제는 기본 코드가 제공되므로 상기 링크를 통해서 문제를 풀어야 합니다.

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

풀이 특징

• 지도 외각을 1로 채운 (n+2)*(n+2) 지도 생성 후 시작
• 출발 -> 도착, 이동 cost 동일: BFS로 접근
• BFS: deque 내 이동가능한 좌표들 삽입하며 확인
• 로봇의 좌표: {(lx, ly), (rx, ry)} 좌표 튜플들을 집합으로 지닌 형태
• 이동했던 좌표인지 확인: visitedPoints 배열을 통해 not in 으로 확인
• deque: (로봇 좌표, 해당 좌표까지의 cost) 값을 지닌 형태
• BFS를 진행하며 현재좌표 기준 이동가능한 좌표들 중 visited 되지 않은 좌표들을 deque 에 삽입 (cost+1)
• 좌표 기준 이동가능한 좌표들을 반환하는 함수 필요
• 총 네가지 값들로 계산
• 상, 하, 좌, 우 이동 확인
• 가로상태에서 세로상태로 회전가능 확인 (y 고정 위, 아래의 x값 모두 0인지 확인)
• 세로상태에서 가로상태로 회전가능 확인 (x 고정 좌, 우의 y값 모두 0인지 확인)

# 최소시간, 이동 cost 가 동일: BFS로 접근
# BFS: deque + 이동가능한 좌표값들 + 이동가능한지 체킹 + cost
# 이동 가능한 좌표값들을 반환하는 함수가 핵심

from collections import deque

# 현재 로봇위치 -> 움직일 수 있는 모든 좌표 리스트 반환
def getNextPoints(points, newBoard):
    canMoves = []
    # 집합 -> 리스트로 변환
    points = list(points)
    lx, ly = points[0][0], points[0][1]
    rx, ry = points[1][0], points[1][1]
    
    # 상, 하, 좌, 우 이동 확인
    for move in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        next_lx, next_ly = lx+move[0], ly+move[1]
        next_rx, next_ry = rx+move[0], ry+move[1]
        # 이동 가능한지 확인 후 canMoves 내 추가
        if newBoard[next_lx][next_ly] == 0 and newBoard[next_rx][next_ry] == 0:
            canMoves.append({(next_lx, next_ly), (next_rx, next_ry)})
            
    # 가로 -> 세로 회전 확인
    if lx == rx:
        # 위, 아래방향 확인
        for move in [1, -1]:
            if newBoard[lx+move][ly] == 0 and newBoard[rx+move][ry] == 0:
                # 좌측 고정, 우측 위, 아래 회전
                canMoves.append({(lx, ly), (lx+move, ly)})
                # 우측 고정, 좌측 위, 아래 회전
                canMoves.append({(rx+move, ry), (rx, ry)})
                
    # 세로 -> 가로 회전 확인
    if ly == ry:
        # 좌, 우방향 확인
        for move in [-1, 1]:
            if newBoard[lx][ly+move] == 0 and newBoard[rx][ry+move] == 0:
                # 위 고정, 아래 좌, 우 회전
                canMoves.append({(lx, ly), (lx, ly+move)})
                # 아래 고정, 위 좌, 우 회전
                canMoves.append({(rx, ry+move), (rx, ry)})
    
    # 최종 이동가능한 Points 집합 리스트 반환
    return canMoves

def solution(board):
    # 테두리 1로 채운 board 로 변환
    n = len(board)
    newBoard = [[1]*(n+2) for _ in range(n+2)]
    for x in range(n):
        for y in range(n):
            newBoard[x+1][y+1] = board[x][y]
    
    # 이동한 위치값들
    startPoints = {(1, 1), (1, 2)}
    visitedPoints = [startPoints]
    # deque: points, cost 값
    q = deque([(startPoints, 0)])
    
    while q:
        # 현재 로봇위치가 n, n 에 닿은 경우
        points, cost = q.popleft()
        if (n, n) in points:
            return cost
        
        # 로봇이 움직일 수 있는 모든 위치 deque 에 추가
        for nextPoints in getNextPoints(points, newBoard):
            if nextPoints not in visitedPoints:
                q.append((nextPoints, cost+1))
                visitedPoints.append(nextPoints)
    return 0