블록 이동하기

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

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

from collections import deque

def solution(board):
    answer = dict() # 위치 체크
    N = len(board)
    board = [[board[y][x] if 0 <= x < N and 0 <= y < N else 1 for x in range(-1, N + 1)] for y in range(-1, N + 1)] # 테두리 padding
    
    def searchCase(info): # 모든 이동과 회전 가능성 판별
        y1, x1, y2, x2 = info
        cases = []

        if y1 == y2: # 가로 모양
            if board[y1 - 1][x1] + board[y2 - 1][x2] == 0: cases += [(y1-1, x1, y2-1, x2), (y1-1, x1, y2, x2-1), (y1-1, x1+1, y2, x2)] # 위쪽 and 회전
            if board[y1 + 1][x1] + board[y2 + 1][x2] == 0: cases += [(y1+1, x1, y2+1, x2), (y1, x1, y2+1, x2-1), (y1, x1+1, y2+1, x2)] # 아래쪽 and 회전
            if board[y1][x1 - 1] == 0: cases += [(y1, x1-1, y2, x2-1)] # 왼쪽
            if board[y2][x2 + 1] == 0: cases += [(y1, x1+1, y2, x2+1)] # 오른쪽
        else: # 세로 모양
            if board[y1 - 1][x1] == 0: cases += [(y1-1, x1, y2-1, x2)] # 위쪽 
            if board[y2 + 1][x2] == 0: cases += [(y1+1, x1, y2+1, x2)] # 아래쪽
            if board[y1][x1 - 1] + board[y2][x2 - 1] == 0: cases += [(y1, x1-1, y2, x2-1), (y1, x1-1, y2-1, x2), (y1+1, x1-1, y2, x2)] # 왼쪽 and 회전
            if board[y1][x1 + 1] + board[y2][x2 + 1] == 0: cases += [(y1, x1+1, y2, x2+1), (y1, x1, y2-1, x2+1), (y1+1, x1, y2, x2+1)] # 오른쪽 and 회전

        return cases
    
    Q = deque([((1, 1, 1, 2), 0)]) # y1, x1, y2, x2, count
    answer[Q[0][0]] = 1
    while Q: # bfs로 완전탐색
        cur, count = Q.popleft()
        caseList = searchCase(cur)
        for case in caseList: # 새로운 경로로만 탐색
            if answer.get(case) is None: Q.append((case, count + 1)); answer[case] = 1
            if case[2:] == (N, N): return count + 1 # (N, N) 도달시 종료

→ 이동 가능성 판별 조건문만 잘 정리하면 기본적인 bfs 완전탐색 문제임