[프로그래머스 Lv3.]블록 이동하기(python)

1. 문제

문제 설명

제한사항

입출력

입출력 예시

---

2. 풀이 과정

내가 생각한 진행 과정

• 로봇이 두칸을 차지하고 있기 때문에 q에 로봇의 위치랑 time(걸린 시간) 넣기

• q를 하나씩 돌면서 진행

  • 로봇이 위치한 두 칸 중에 한칸이라도 (n, n)에 도착하면 끝내기
  • q를 하나씩 돌리면서 다음 위치가 가능한 애들을 next_position 함수를 이용해서 가지고오면 visited에 넣고, q에 해당 위치와 time+1을 넣어줌
  • visited는 갔던 곳을 다시 가지 않기 위해 표시해주는 것

• new_board 만들기

  • 로봇은 가로/세로로 이동할 수 있고, 오/왼/위/아래로 이동 가능
  • 이때, board의 맨 윗칸에 있는 경우, 위로 움직이면 에러 + 가로->세로로 이동할 때 위로 이동하면 에러 -> 에외처리 하나하나 해줘야함
  • 이 예외처리를 한번에 할 수 있는 방법이 가쪽에 1(이동할 수 없는 자리)로 가득채운 벽을 세운다.

• 로봇의 다음 위치 파악을 위한 함수(next_position)

  • 상하좌우 이동: 로봇이 갈 위치의 board가 모두 0이라면 이동

  • 가로 -> 세로 회전(if x1 == x2:)

    • 밑으로 회전할 수도 있지만, 위로 회전할 수도 있음(for a in [1, -1]: 이동방향 작성)
    • 만약, 아래로 회전한다면, 밑에 두칸이 모두 0이여야 우선 이동 가능.
    • 로봇 위치가 1,2일 때 아래로 회전한다면 로봇이 1,3도 가능 2,4도 가능 -> 두 경우 모두 temp에 넣어줌

  • 세로 -> 가로 회전(if y1 == y2:)

    • 가로 -> 세로 회전 경우와 동일

코드

from collections import deque

def next_position(robot, board):
    temp = []  # 다음번에 갈 수 있는 곳 모두 넣기
    near = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    (x1, y1), (x2, y2) = robot

    # 1. 상하좌우 이동
    for i in range(4):
        if board[x1 + near[i][0]][y1 + near[i][1]] == 0 and board[x2 + near[i][0]][y2 + near[i][1]] == 0:
            temp.append({(x1 + near[i][0], y1 + near[i][1]), (x2 + near[i][0], y2 + near[i][1])})

    # 2. 가로 -> 세로 회전
    if x1 == x2:
        for a in [1, -1]:  # 만약 (1,2)에서 -1이 된다면 에러남 -> 4방면 가쪽에 벽하나 세우기
            if board[x1 + a][y1] == 0 and board[x2 + a][y2] == 0:
                temp.append({(x1, y1), (x1 + a, y1)})
                temp.append({(x2, y2), (x2 + a, y2)})

    # 3. 세로 -> 가로 회전
    if y1 == y2:
        for b in [1, -1]:
            if board[x1][y1 + b] == 0 and board[x2][y2 + b] == 0:
                temp.append({(x1, y1), (x1, y1 + b)})
                temp.append({(x2, y2), (x2, y2 + b)})

    return temp


def solution(board):
    n = len(board)
    new_board = [[1] * (n+2) for _ in range(n+2)]
    for i in range(n):
        for j in range(n):
            new_board[i+1][j+1] = board[i][j]

    # 현재 좌표 위치 큐 삽입, 확인용 set
    q = deque([])
    robot = {(1, 1), (1, 2)}
    visited = []
    q.append((robot, 0))
    visited.append(robot)

    while q:
        robot, time = q.popleft()

        if (n, n) in robot:  # 종점 도착
            return time

        # bfs 진행
        for location in next_position(robot, new_board):
            if location not in visited:
                visited.append(location)
                q.append((location, time+1))