[프로그래머스] 블록 이동하기 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

 

막상 풀고보니 그렇게 어려운 문제가 아닌듯 했다.

물론 생각하는데 좀 걸렸지만, 그래도 두시간정도 걸린듯 하다.

 

로봇을 상하좌우, 회전하여 n,n칸으로 이동할 때 최소 시간을 구하는 문제이다.

로봇의 좌표가 두개이고 n의 크기가 100으로 작아서 4차원 배열로 방문 체크를 했다.

 

최소 시간을 구하라해서 BFS를 이용했다.

 

로봇의 이동은 그냥 두좌표 동시에 상하좌우 이동시키고 유효성 검증 후에 체크 및 큐에 넣어주면 된다.

 

 

문제는 로봇 회전이다.

나는 그냥 ㅡ, ㅣ 모양 각각 좌표를 돌려서 체크했다.

주황선이 현재 로봇 모양이고 빨간선이 로봇을 회전했을 때 가능한 모양이다.

각 빨간선의 좌표들과 회전 시 봐야하는 좌표를 계산해서 유효성 검사후에 방문 체크 및 큐에 넣어줬다.

좌표 계산은 x,y를 적절히 +1,-1 하면 된다. 코드를 보면 알 수 있다.

 

이동도중 끝점이 n,n점에 도달하면 시간을 리턴해줬다.

 

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def solution(board):
    global n
    n = len(board)
    return bfs(board)


def bfs(board):
    q = deque([(0, 0, 0, 1, 0, 0)])
    visited = [[[[False] * n for _ in range(n)] for _ in range(n)] for _ in range(n)]

    visited[0][0][0][1] = True

    while q:
        x1, y1, x2, y2, cnt, typ = q.pop()
        if x2 == y2 == n - 1:
            return cnt
        for d in range(4):
            nx1 = x1 + dx[d]
            ny1 = y1 + dy[d]

            nx2 = x2 + dx[d]
            ny2 = y2 + dy[d]

            if point_validator(nx1, ny1, nx2, ny2, board, visited):
                visited[nx1][ny1][nx2][ny2] = True
                q.appendleft((nx1, ny1, nx2, ny2, cnt + 1, typ))

        for r in range(4):
            nx1, ny1, nx2, ny2, nx3, ny3 = rotate_robot(x1, y1, x2, y2, typ, r)

            if rotate_validator(nx3,ny3,board) and point_validator(nx1, ny1, nx2, ny2, board, visited):
                visited[nx1][ny1][nx2][ny2] = True
                q.appendleft((nx1, ny1, nx2, ny2, cnt + 1, (typ+1)%2))

def rotate_robot(x1, y1, x2, y2, typ, r):
    if typ == 0:
        if r == 0:
            return x1, y1, x1 + 1, y1, x2 + 1, y2
        elif r == 1:
            return x1 - 1, y1, x1, y1, x2 - 1, y2
        elif r == 2:
            return x2, y2, x2 + 1, y2, x1 + 1, y1
        elif r == 3:
            return x2 - 1, y2, x2, y2, x1 - 1, y1
    elif typ == 1:
        if r == 0:
            return x1, y1 - 1, x1, y1, x2, y2 - 1
        elif r == 1:
            return x1, y1, x1, y1 + 1, x2, y2 + 1
        elif r == 2:
            return x2, y2 - 1, x2, y2, x1, y1 - 1
        elif r == 3:
            return x2, y2, x2, y2 + 1, x1, y1 + 1

def rotate_validator(x,y,board):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    elif board[x][y] == 1:
        return False
    return True

def point_validator(x1, y1, x2, y2, board, visited):
    if x1 < 0 or y1 < 0 or x2 < 0 or y2 < 0 or x1 >= n or y1 >= n or x2 >= n or y2 >= n:
        return False
    elif board[x1][y1] == 1 or board[x2][y2] == 1:
        return False
    elif visited[x1][y1][x2][y2]:
        return False
    return True