문제 링크

https://programmers.co.kr/learn/courses/30/lessons/60063

문제 설명

• 두 칸을 차지하는 로봇이 있음
• 가로 -> 세로, 세로 -> 가로 회전 가능
• 회전 조건 있음
• 끝 점까지 이동할 때 걸리는 시간 리턴

풀이

• 너비 우선 탐색
• visited 를 set으로 두고 두 점을 모두 저장
• 조건에 따라 인접한 위치 판별

코드

from collections import deque


def solution(board):
    answer = bfs(len(board), board)
    return answer


def bfs(n, board):
    q = deque([(0, 0, 0, 1, 0)])
    visited = set([(0, 0, 0, 1)])
    while q:
        y1, x1, y2, x2, level = q.popleft()
        # 끝에 도달하면
        if (y1 == n-1 and x1 == n-1) or (y2 == n-1 and x2 == n-1):
            return level
        for i in range(12):
            # 가로 세로 구분
            if (x1 != x2 and 8 <= i < 12) or (y1 != y2 and 4 <= i < 8):
                continue
            ny1, nx1, ny2, nx2 = get_next((y1, x1, y2, x2), i)
            if (0 <= ny1 < n and 0 <= nx1 < n) and (0 <= ny2 < n and 0 <= nx2 < n):
                if possible(n, board, (y1, x1, y2, x2), i):
                    if (ny1, nx1, ny2, nx2) not in visited:
                        visited.add((ny1, nx1, ny2, nx2))
                        q.append((ny1, nx1, ny2, nx2, level + 1))
    return 0


def get_next(pos, i):
    y1, x1, y2, x2 = pos
    d = [
        (-1, 0, -1, 0), # 위
        (1, 0, 1, 0),   # 아래
        (0, -1, 0, -1), # 왼
        (0, 1, 0, 1),   # 오
        (-1, 0, 0, -1), # 가로일 때 위
        (-1, 1, 0, 0),  # 가로일 때 위
        (0, 0, 1, -1),  # 가로일 때 아래
        (0, 1, 1, 0),   # 가로일 때 아래
        (0, -1, -1, 0), # 세로일 때 왼
        (1, -1, 0, 0),  # 세로일 때 왼
        (1, 0, 0, 1),   # 세로일 때 오
        (0, 0, -1, 1),  # 세로일 때 오
    ]
    ny1 = y1 + d[i][0]
    nx1 = x1 + d[i][1]
    ny2 = y2 + d[i][2]
    nx2 = x2 + d[i][3]
    return ny1, nx1, ny2, nx2


# 벽이 있는지
def possible(n, board, pos, i):
    y1, x1, y2, x2 = pos
    # 위
    if i == 0 and (board[y1-1][x1] or board[y2-1][x2]):
        return False
    # 아래
    if i == 1 and (board[y1+1][x1] or board[y2+1][x2]):
        return False
    # 왼
    if i == 2 and (board[y1][x1-1] or board[y2][x2-1]):
        return False
    # 오
    if i == 3 and (board[y1][x1+1] or board[y2][x2+1]):
        return False
    # 가로일 때 위
    if 4 <= i < 6 and (board[y1-1][x1] or board[y2-1][x2]):
        return False
    # 가로일 때 아래
    if 6 <= i < 8 and (board[y1+1][x1] or board[y2+1][x2]):
        return False
    # 세로일 때 왼
    if 8 <= i < 10 and (board[y1][x1-1] or board[y2][x2-1]):
        return False
    # 세로일 때 오
    if 10 <= i < 12 and (board[y1][x1+1] or board[y2][x2+1]):
        return False
    return True