[프로그래머스] 블록 이동하기 - python

https://school.programmers.co.kr/learn/courses/30/lessons/60063?language=python3 

프로그래머스

회전을 같이 생각하는 게 너무 까다로운 문제..

---

코드 설명

from collections import deque

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


def get_next_pos(pos, board, N):
    pos1, pos2 = pos
    (pos1x, pos1y), (pos2x, pos2y) = pos1, pos2
    npos = []
    # 상하좌우
    for d in range(4):
        n1x, n1y = pos1x + dx[d], pos1y + dy[d]
        n2x, n2y = pos2x + dx[d], pos2y + dy[d]
        if n1x < 0 or n1x > N - 1 or n1y < 0 or n1y > N - 1 or n2x < 0 or n2x > N - 1 or n2y < 0 or n2y > N - 1:
            continue
        if board[n1x][n1y] == 0 and board[n2x][n2y] == 0:
            npos.append(set(((n1x, n1y), (n2x, n2y))))
    
    # 가로일 때 회전
    if pos1x == pos2x:
        # 아래로
        if pos1x + 1 <= N - 1:
            if board[pos1x + 1][pos1y] == 0 and board[pos2x + 1][pos2y] == 0:
                npos.append(set(((pos1x, pos1y), (pos2x + 1, pos1y))))
                npos.append(set(((pos1x + 1, pos2y), (pos2x, pos2y))))
        # 위로
        if pos1x - 1 >= 0:
            if board[pos1x - 1][pos1y] == 0 and board[pos2x - 1][pos2y] == 0:
                npos.append(set(((pos1x, pos1y), (pos2x - 1, pos1y))))
                npos.append(set(((pos1x - 1, pos2y), (pos2x, pos2y))))

    # 세로일 때 회전
    elif pos1y == pos2y:
        # 오른쪽으로
        if pos1y + 1 <= N - 1:
            if board[pos1x][pos1y + 1] == 0 and board[pos2x][pos2y + 1] == 0:
                npos.append(set(((pos1x, pos1y), (pos1x, pos2y + 1))))
                npos.append(set(((pos2x, pos1y + 1), (pos2x, pos2y))))
        # 왼쪽으로
        if pos1y - 1 >= 0:
            if board[pos1x][pos1y - 1] == 0 and board[pos2x][pos2y - 1] == 0:
                npos.append(set(((pos1x, pos1y), (pos1x, pos2y - 1))))
                npos.append(set(((pos2x, pos1y - 1), (pos2x, pos2y))))

    return npos



def solution(board):
    robot = set(((0, 0), (0, 1)))   # 로봇 초기 좌표
    q = deque()
    q.append((robot, 0))            # 로봇 위치, cost
    visited = [robot]               # 이미 방문한 좌표
    N = len(board)

    while q:
        pos, cost = q.popleft()     # 현재 위치, 비용
        # 현재 위치에서 갈 수 있는 점들(상하좌우, 회전)
        npos = get_next_pos(pos, board, N)
        for nq in npos:
            if (N - 1, N - 1) in nq:    # 종료 조건, 마지막에 이동한거 횟수 증가 안 돼서 + 1 
                return cost + 1
            if nq in visited:           # 이미 방문한 곳이면 x
                continue
            visited.append(nq)          # 방문 추가
            q.append((nq, cost + 1))    # 후보군에 추가


print(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]]))

 

---

코드 결과

 

 

---

참고) 이것이 코딩 테스트다 with 파이썬 (나동빈 지음)