Programmers - 블록 이동하기

문제 링크

BFS로 최단거리를 탐색하는데, 상하좌우 이동만이 아니라 '회전'이라는 선택이 추가된 문제이다.

가로상태를 mode 0, 세로상태를 mode 1로 정의하고, 좌표를 로봇의 좌측 최상단을 기준으로 잡았다.
방문 상태를 단지 x,y에 방문했는지 뿐만 아니라 어떤 mode인 상태로 방문했는지도 체크해야 하기 때문에
visit을 3차원 배열로 만들었다.

처음에는 기준점만 축으로 계산하고 문제를 풀었다가, 실패 후 문제 예시를 다시 보고 빠트린 점을 찾을 수 있었다.
기준점을 축으로 시계방향 회전이 가능하다는 것은 다른 한 점을 기준으로 반시계 방향이 가능하다는 것이다.

rotate()에 다른 점을 기준으로 반시계 방향한 결과를 같이 넣어주니까 테스트를 모두 통과했다.

from collections import deque


def solution(board):
    n = len(board)
    # 가로 0, 세로 1
    visit = [[[False, False] for _ in range(n)] for __ in range(n)]
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def is_zero_and_in_range(pos):
        (x, y) = pos
        if not (0 <= x < n and 0 <= y < n):
            return False
        return board[x][y] == 0

    def can_rotate(pos, clockwise):
        (x, y, mode) = pos
        if mode == 0:
            xdiff = 1 if clockwise else -1
            positions = [(x+xdiff, y), (x+xdiff, y+1)]
            for position in positions:
                if not is_zero_and_in_range(position):
                    return False
        else:
            ydiff = -1 if clockwise else 1
            positions = [(x, y+ydiff), (x+1, y+ydiff)]
            for position in positions:
                if not is_zero_and_in_range(position):
                    return False

        return True

    def rotate(pos, clockwise):
        # 한 점을 축으로 시계방향 회전이 가능하면
        # 다른 힌 점을 축으로 반시계 방향 회전이 가능하다

        (x, y, mode) = pos
        if mode == 0:
            xdiff = 0 if clockwise else -1
            return [(x+xdiff, y, 1), (x+xdiff, y+1, 1)]
        else:
            ydiff = -1 if clockwise else 0
            return [(x, y+ydiff, 0), (x+1, y+ydiff, 0)]

    def can_move(pos, dir):
        (x, y, mode) = pos
        (dx, dy) = dir
        ax = x+dx
        ay = y+dy
        next = [(ax, ay)]
        if mode == 0:
            next.append((ax, ay+1))
        else:
            next.append((ax+1, ay))

        for position in next:
            if not is_zero_and_in_range(position):
                return False
        return True

    def move(pos, dir):
        (x, y, mode) = pos
        (dx, dy) = dir
        return (x+dx, y+dy, mode)

    # bfs
    q = deque()
    q.append((0, 0, 0))
    visit[0][0][0] = True

    count = 0
    while len(q) > 0:
        for i in range(len(q)):
            current = q.popleft()
            (x, y, mode) = current

            # 도착
            if mode == 0 and x == n-1 and y == n-2:
                return count
            if mode == 1 and x == n-2 and y == n-1:
                return count

            # 회전
            for clockwise in [True, False]:
                if can_rotate(current, clockwise):
                    rotated = rotate(current, clockwise)
                    for (rx, ry, rmode) in rotated:
                        if visit[rx][ry][rmode]:
                            continue
                        visit[rx][ry][rmode] = True
                        q.append((rx, ry, rmode))
            # 이동
            for dir in dirs:
                if can_move(current, dir):
                    (mx, my, mmode) = move(current, dir)
                    if visit[mx][my][mmode]:
                        continue
                    visit[mx][my][mmode] = True
                    q.append((mx, my, mmode))

        count += 1

    return -1