[프로그래머스] 블록 이동하기 / 2020 카카오 블라인드 채용 / python

쉽게 보면 BFS로 마지막에 도달했을 때의 이동 카운트를 반환하면 되는 문제이지만, 조건이 까다로웠다.

우선 로봇은 두 칸을 차지하기 때문에 방문한 좌표는 set에 ((x1, y1), (x2, y2)) 형태로 넣어주었다.(리스트는 존재 여부를 판단할 때 평균적으로 O(n)의 시간이 들지만 set은 O(1)의 시간이 든다)

그리고 만족해야 하는 조건을 두 가지로 나눠서 생각해보았다.

첫번째는 상하좌우로 이동할 때

• 현재 차지한 두 칸에서 상하좌우로 이동할 수 있는 다음 위치가 있다면 큐에 넣는다.(몸 두 칸이 전부 벽에 있으면 안되고 필드 밖에 나가면 안됨)

두번째는 회전할 때

• 회전을 할 때 걸리게 되는 위치(현재 위치와 회전을 한 위치 사이)에 벽이 존재하면 회전으로 이동할 수 없다.
• 현재 차지한 두 칸에서 회전할 수 있는 방법은 4가지가 있는데 이 4가지 중에 이동할 수 있는 다음 위치가 있다면 큐에 넣는다.(몸 두 칸이 전부 벽에 있으면 안되고 필드 밖에 나가면 안됨)

설명은 간단하지만 구현을 할 때에는 실수할 수 있는 부분들이 많아서 실수하지 않기 위해 조건문을 모두 함수로 빼서 가독성을 높였다.

 

from collections import deque

EXIST = 1
NOT_EXIST = 0


def solution(board):
    def move(_next1, _next2, _count, _isRow, _passing=(0, 0)):
        if isVisited(visited, _next1, _next2) or not isPossibleMove(board, _next1, _next2) or not isPossibleTurn(board, _passing):
            return
        q.append((_next1, _next2, _count + 1, _isRow))
        visited.add((_next1, _next2))

    answer = 0
    n = len(board)
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    turns = [1, -1]
    visited = set()
    q = deque()
    q.append(((0, 0), (0, 1), 0, True))

    while q:
        cur1, cur2, count, isRow = q.popleft()

        if isOnEndPoint(n, cur1, cur2):
            return count

        for dir in range(4):
            move((cur1[0] + dy[dir], cur1[1] + dx[dir]), (cur2[0] + dy[dir], cur2[1] + dx[dir]), count, isRow)

        if isRow:
            for turn in turns:
                move(cur1, (cur1[0] + turn, cur1[1]), count, False, (cur2[0] + turn, cur2[1]))
                move((cur2[0] + turn, cur2[1]), cur2, count, False, (cur1[0] + turn, cur1[1]))
        else:
            for turn in turns:
                move(cur1, (cur1[0], cur1[1] + turn), count, True, (cur2[0], cur2[1] + turn))
                move((cur2[0], cur2[1] + turn), cur2, count, True, (cur1[0], cur1[1] + turn))

    return answer


def isVisited(visited, spot1, spot2):
    return True if (spot1, spot2) in visited or (spot2, spot1) in visited else False


def isPossibleMove(board, spot1, spot2):
    return False if not isInFieldRobot(len(board), spot1, spot2) or not isInRoad(board, spot1, spot2) else True


def isPossibleTurn(board, passing):
    return True if board[passing[0]][passing[1]] == 0 else False


def isInRoad(board, spot1, spot2):
    return False if board[spot1[0]][spot1[1]] == 1 or board[spot2[0]][spot2[1]] == 1 else True


def isInFieldRobot(n, spot1, spot2):
    return False if not isInField(n, spot1[0], spot1[1]) or not isInField(n, spot2[0], spot2[1]) else True


def isInField(n, y, x):
    return False if y < 0 or y > n-1 or x < 0 or x > n-1 else True


def isOnEndPoint(n, spot1, spot2):
    return True if (spot1[0] == n-1 and spot1[1] == n-1) or (spot2[0] == n-1 and spot2[1] == n-1) else False