[Python] 블록 이동하기

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

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

---

1. 이해하기

• (1,1)에서 시작하여 (N,N)에 도착하는데 걸리는 최소 시간을 구해야 한다.
• 로봇은 두 칸을 차지한다.
• 로봇은 회전과 이동이 가능하다.
  • 회전 시 조건에 맞아야 회전이 가능하다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어진다.

---

2. 구현하기

• 걸리는 최소 시간을 구하기 위해서는 BFS를 이용하여 구현이 가능하다. 그 이유는 회전, 이동 모두 가중치가 1이기 때문이다.
• 로봇은 기본적으로 두 칸을 차지하는데 (N,N)에 가까운 점을 이용해 로봇을 움직이고 이미 확인했던 것인지 체크를 한다.
  • 로봇의 두 지점을 확인하지 않는 이유는 가까운 점만 놓고 로봇이 어떻게 놓여있는지만 안다면 로봇이 어떤 지점에 놓여있는지는 명확하기 때문이다.
• 로봇의 회전과 이동을 신경 써줘야한다. 회전은 로봇의 앞(N,N에서 가까운 점)과 로봇의 뒤(N,N에서 먼 점) 둘의 회전을 모두 신경써줘야 한다.

• 이때 회전이 가능한지 여부(바로 아래 혹은 위가 빈칸, 옮기는 지역이 빈칸)를 확인해준다
• 로봇이 어떻게 놓여있는지는 0과 1을 이용해 0이면 가로로, 1이면 세로로 놓여있다고 판단했다.

---

3. 전체 코드

from collections import deque

def solution(board):
    N = len(board)
    answer = 0
    q = deque()
    q.append((0,1,0,0)) # (0,1) -
    visited = [[[False]*2 for _ in range(N)] for _ in range(N)]
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while q:
        x,y,d,dist = q.popleft()
        if x == N-1 and y == N-1:
            answer = dist
            break
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= N or visited[nx][ny][d] or board[nx][ny] == 1:
                continue
            if (d == 0 and ny-1 < 0) or (d == 1 and nx-1 < 0):
                continue
            if (d == 0 and board[nx][ny-1] == 1) or (d == 1 and board[nx-1][ny] == 1):
                continue
            q.append((nx,ny,d,dist+1))
            visited[nx][ny][d] = True
        if d == 0:
            if x > 0 and board[x-1][y-1] == 0 and board[x-1][y] == 0 and not visited[x][y][1]:
                q.append((x,y,1,dist+1))
                visited[x][y][1] = True
            if x < N-1 and board[x+1][y-1] == 0 and board[x+1][y] == 0 and not visited[x+1][y][1]:
                q.append((x+1,y,1,dist+1))
                visited[x+1][y][1] = True
            if x > 0 and board[x-1][y] == 0 and board[x-1][y-1] == 0 and not visited[x][y-1][1]:
                q.append((x,y-1,1,dist+1))
                visited[x][y-1][1] = True
            if x < N-1 and board[x+1][y] == 0 and board[x+1][y-1] == 0 and not visited[x+1][y-1][1]:
                q.append((x+1,y-1,1,dist+1))
                visited[x+1][y-1][1] = True
        if d == 1:
            if y > 0 and board[x-1][y-1] == 0 and board[x][y-1] == 0 and not visited[x][y][0]:
                q.append((x,y,0,dist+1))
                visited[x][y][0] = True
            if y < N-1 and board[x-1][y+1] == 0 and board[x][y+1] == 0 and not visited[x][y+1][0]:
                q.append((x,y+1,0,dist+1))
                visited[x][y+1][0] = True
            if y > 0 and board[x][y-1] == 0 and board[x-1][y-1] == 0 and not visited[x-1][y][0]:
                q.append((x-1,y,0,dist+1))
                visited[x-1][y][0] = True
            if y < N-1 and board[x][y+1] == 0 and board[x-1][y+1] == 0 and not visited[x-1][y+1][0]:
                q.append((x-1,y+1,0,dist+1))
                visited[x-1][y+1][0] = True
    return answer

solution([[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]])