블록 이동하기 파이썬

from collections import deque


def rotate(lr, lc, rr, rc, board):
    locs = []

    for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
        nlr, nlc, nrr, nrc = lr + dr, lc + dc, rr + dr, rc + dc
        if board[nlr][nlc] == 1 or board[nrr][nrc] == 1:
            continue
        locs.append((nlr, nlc, nrr, nrc))

    if lr == rr:
        if lc < rc:
            if board[lr - 1][lc + 1] == 0 and board[lr - 1][lc] == 0:  # 반시계
                locs.append((lr, lc, lr - 1, lc))
            if board[lr + 1][lc + 1] == 0 and board[lr + 1][lc] == 0:  # 시계
                locs.append((lr, lc, lr + 1, lc))
        else:
            if board[lr + 1][lc - 1] == 0 and board[lr + 1][lc] == 0:  # 반시계
                locs.append((lr, lc, lr + 1, lc))
            if board[lr - 1][lc - 1] == 0 and board[lr - 1][lc] == 0:  # 시계
                locs.append((lr, lc, lr - 1, lc))

    else:
        if lr < rr:
            if board[lr + 1][lc + 1] == 0 and board[lr][lc + 1] == 0:  # 반시계
                locs.append((lr, lc, lr, lc + 1))
            if board[lr + 1][lc - 1] == 0 and board[lr][lc - 1] == 0:  # 시계
                locs.append((lr, lc, lr, lc - 1))
        else:
            if board[lr - 1][lc - 1] == 0 and board[lr][lc - 1] == 0:  # 반시계
                locs.append((lr, lc, lr, lc - 1))
            if board[lr - 1][lc + 1] == 0 and board[lr][lc + 1] == 0:  # 시계
                locs.append((lr, lc, lr, lc + 1))

    return locs


def solution(board):
    n = len(board)
    board = [[1] * (n + 2)] + [[1] + b + [1] for b in board] + [[1] * (n + 2)]
    q = deque([[1, 1, 1, 2, 0]])
    visited = set()

    while q:
        lr, lc, rr, rc, cnt = q.popleft()
        if (lr, lc, rr, rc) in visited:
            continue
        if (lr, lc) == (n, n) or (rr, rc) == (n, n):
            return cnt
        visited.add((lr, lc, rr, rc))

        for loc in rotate(lr, lc, rr, rc, board) + rotate(rr, rc, lr, lc, board):
            q.append([*loc, cnt + 1])

최단경로 => bfs

하지만 이문제는 좌표를 두개 차지한다는 점과, 회전시킨다는 조건이 있어서 구현이 어려웠음

기계를 왼쪽, 오른쪽으로 나눠서 왼쪽을 축으로 회전하고, 오른쪽을 축으로 한번 더 회전해야한다.

따라서 rotate 함수를 두번 사용했다. 

 

 

 

밑에 코드는 rotate 함수를 좀 더 간단하게 줄인 코드

from collections import deque


def rotate(lr, lc, rr, rc, board):
    locs = []

    for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
        nlr, nlc, nrr, nrc = lr + dr, lc + dc, rr + dr, rc + dc
        if board[nlr][nlc] == 1 or board[nrr][nrc] == 1:
            continue
        locs.append((nlr, nlc, nrr, nrc))

    if lr == rr:
        for i in [-1, 1]:
            if board[lr + i][lc] == 0 and board[rr + i][rc] == 0:
                locs.append((lr, lc, lr + i, lc))
                locs.append((rr, rc, rr + i, rc))
    else:
        for i in [-1, 1]:
            if board[lr][lc + i] == 0 and board[rr][rc + i] == 0:
                locs.append((lr, lc + i, lr, lc))
                locs.append((rr, rc + i, rr, rc))
    return locs


def solution(board):
    n = len(board)
    board = [[1] * (n + 2)] + [[1] + b + [1] for b in board] + [[1] * (n + 2)]
    q = deque([[1, 1, 1, 2, 0]])
    visited = set()

    while q:
        lr, lc, rr, rc, cnt = q.popleft()
        if (lr, lc, rr, rc) in visited:
            continue
        if (lr, lc) == (n, n) or (rr, rc) == (n, n):
            return cnt
        visited.add((lr, lc, rr, rc))

        for loc in rotate(lr, lc, rr, rc, board):
            q.append([*loc, cnt + 1])

 

축을 왼쪽으로 하든 오른쪽으로 하든 회전이 가능하다면, 반대쪽 축에서도 회전이 가능한 것을 이용해

rotate 함수를 좀더 간단하게 만들 수 있었다.