title: "[프로그래머스] 블록 이동하기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/60063"
description: "프로그래머스 Level 3 문제 [블록 이동하기]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from queue import deque

N = -1
A = None

def is_valid(r1, c1, r2=None, c2=None):
    if r2 is not None and c2 is not None:
        tmp = (0 <= r1 < N) and (0 <= c1 < N) and (0 <= r2 < N) and (0 <= c2 < N)
        return tmp and A[r1][c1] == 0 and A[r2][c2] == 0
    else:
        return (0 <= r1 < N) and (0 <= c1 < N) and A[r1][c1] == 0

def solution(board):
    global N, A
    N = len(board)
    A = board
    # 복잡해 보이지만, 상하좌우 이동 4가지,
    # 왼쪽/오른쪽 혹은 위쪽/아래쪽 축으로 시계/반시계 회전 4가지 총 8가지
    # 움직임이 있는 bfs로 해결해봅니다.
    q, vis = deque(), set()
    # (d, r1, c1, r2, c2)를 큐에 넣습니다.
    # 항상 r1 <= r2, c1 <= c2가 되도록 합니다. 
    q.append( (0, 0, 0, 0, 1) )
    vis.add( (0, 0, 0, 1) )
    while q:
        d, r1, c1, r2, c2 = q.popleft()
        
        # 목적지에 도달했으면 이동 거리를 리턴합니다.
        if r2 == N-1 and c2 == N-1:
            return d
        
        # 평행이동
        # r1, c1, r1, c2의 대소 관계가 보존됩니다.
        moves = [
            # dr1, dc1, dr2, dc2
            (0, 1, 0, 1), # 오른쪽
            (0, -1, 0, -1), # 왼쪽
            (-1, 0, -1, 0), # 위쪽
            (1, 0, 1, 0), # 아래쪽
        ]
        for dr1, dc1, dr2, dc2 in moves:
            state = (r1+dr1, c1+dc1, r2+dr2, c2+dc2)
            if is_valid(*state) and state not in vis:
                q.append( (d+1, *state) )
                vis.add(state)
        
        # 회전
        # 1. 가로로 놓여있는 경우
        if r1 == r2:
            # 1-1. 왼쪽 축, 반시계방향 회전
            state = (r2-1, c2-1, r1, c1)
            if is_valid(*state) and state not in vis and is_valid(r2-1, c2):
                q.append( (d+1, *state) )
                vis.add(state)
            
            # 1-2. 왼쪽 축, 시계방향 회전
            state = (r1, c1, r2+1, c2-1)
            if is_valid(*state) and state not in vis and is_valid(r2+1, c2):
                q.append( (d+1, *state) )
                vis.add(state)
            
            # 1-3. 오른쪽 축, 시계방향 회전
            state = (r1-1, c1+1, r2, c2)
            if is_valid(*state) and state not in vis and is_valid(r1-1, c1):
                q.append( (d+1, *state) )
                vis.add(state)
            
            # 1-4. 오른쪽 축, 반시계방향 회전
            state = (r2, c2, r1+1, c1+1)
            if is_valid(*state) and state not in vis and is_valid(r1+1, c1):
                q.append( (d+1, *state) )
                vis.add(state)
                
        # 2. 세로로 놓인 경우
        else:
            # 2-1. 위쪽 축, 시계방향 회전
            state = (r2-1, c2-1, r1, c1)
            if is_valid(*state) and state not in vis and is_valid(r1+1, c1-1):
                q.append( (d+1, *state) )
                vis.add(state)
            
            # 2-2. 위쪽 축, 반시계방향 회전
            state = (r1, c1, r2-1, c2+1)
            if is_valid(*state) and state not in vis and is_valid(r1+1, c1+1):
                q.append( (d+1, *state) )
                vis.add(state)
            
            # 2-3. 아래쪽 축, 시계방향 회전
            state = (r2, c2, r1+1, c1+1)
            if is_valid(*state) and state not in vis and is_valid(r2-1, c2+1):
                q.append( (d+1, *state) )
                vis.add(state)
            
            # 2-4. 아래쪽 축, 반시계방향 회전
            state = (r1+1, c1-1, r2, c2)
            if is_valid(*state) and state not in vis and is_valid(r2-1, c2-1):
                q.append( (d+1, *state) )
                vis.add(state)

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges