[프로그래머스/파이썬] 블록 이동하기(60063) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 블록 이동하기(60063)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

2칸짜리 로봇 블록을 이동/회전시켜 목표 위치 (n-1, n-1)에 도달하는 최소 시간을 구하는 문제입니다.

코드

from collections import deque

def solution(board):    
    n = len(board)
    
    q = deque([((0, 0), (0, 1), 0)])
    enQ = q.append
    deQ = q.popleft
    visited = set([q[0][:-1]])
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

    while q:
        a, b, t = deQ()
        if b[0] == b[1] == n-1: return t
        for d in directions:
            try:
                na, nb = (a[0]+d[0], a[1]+d[1]), (b[0]+d[0], b[1]+d[1])
                if -1 in [*na, *nb]: raise IndexError
                if a > b: a, b = b, a
                
                if board[na[0]][na[1]] == board[nb[0]][nb[1]] != 1 and\
                   (na, nb) not in visited:
                    enQ((na, nb, t+1))
                    visited.add((na, nb))
                    
            except IndexError: continue

        if a[0] == b[0] < n-1:
            is_rotatable = True
            for i in range(2):
                for j in range(2):
                    is_rotatable &= board[a[0]+i][a[1]+j] != 1
            if is_rotatable:
                for c in [a, b]:
                    na, nb = c, (c[0]+1, c[1])
                    if (na, nb) not in visited:
                        enQ((na, nb, t+1))
                        visited.add((na, nb))


        if a[0] == b[0] > 0:
            is_rotatable = True
            for i in range(2):
                for j in range(2):
                    is_rotatable &= board[a[0]-i][a[1]+j] != 1
            if is_rotatable:
                for c in [a, b]:
                    na, nb = (c[0]-1, c[1]), c
                    if (na, nb) not in visited:
                        enQ((na, nb, t+1))
                        visited.add((na, nb))
                    
        if a[1] == b[1] < n-1:
            is_rotatable = True
            for i in range(2):
                for j in range(2):
                    is_rotatable &= board[a[0]+i][a[1]+j] != 1
            if is_rotatable:
                for c in [a, b]:
                    na, nb = c, (c[0], c[1]+1)
                    if (na, nb) not in visited:
                        enQ((na, nb, t+1))
                        visited.add((na, nb))
                        
        if a[1] == b[1] > 0:
            is_rotatable = True
            for i in range(2):
                for j in range(2):
                    is_rotatable &= board[a[0]+i][a[1]-j] != 1
            if is_rotatable:
                for c in [a, b]:
                    na, nb = (c[0], c[1]-1), c
                    if (na, nb) not in visited:
                        enQ((na, nb, t+1))
                        visited.add((na, nb))

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

설명

BFS 큐에 (블록 좌표 2개, 시간)을 넣어 최단 시간을 탐색합니다.

매 단계에서:

• 4방향 평행 이동
• 가로/세로 상태에 따른 회전 이동

가능 여부를 검사하고, 방문하지 않은 상태만 큐에 추가합니다. 처음 목표 칸에 도달한 시간이 정답입니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---