[Python] 프로그래머스 / 2020 KAKAO BLIND RECRUITMENT / 블록 이동하기

문제 링크

 

쉽게 쉽게

로봇은 두 칸을 차지하며, 상하좌우로 움직일 수 있고, 90도로 회전할 수 있다. 이때 로봇 두 칸 모두 회전의 축이 될 수 있다. 일단은 로봇의 위치를 다음과 같이 저정할 것이다.

 

가로로 있으면 False, 세로로 있으면 True로 저장하고, 두 칸 중 X축, Y축 값이 더 작은 좌표를 대표위치값으로 저장할 것이다.

 

또한 회전을 위해서는 조건 체크를 꼼꼼히 해야 한다:

 

 

회전을 하면 좌표값은 다음과 같이 된다:

 

 

회전하는 그림을 합쳐보면 :

 

즉, 회전을 위해서는 남동, 남서, 북동 방향을 탐색하고, 북서 방향은 탐색할 필요 없다.

회전을 위한 if문이 길어지는 걸 방지하기 위해 컨디션 변수를 선언하여 이를 if문에 활용할 것이다.

#컨디션 변수들 먼저 선언
south_east = cx < N-1 and cy < N-1 and not (board[cx][cy] or board[cx+1][cy] or board[cx][cy+1] or board[cx+1][cy+1])
north_east = cx > 0 and cy < N-1 and not (board[cx][cy] or board[cx-1][cy] or board[cx][cy+1] or board[cx-1][cy+1])
south_west = cx < N-1 and cy > 0 and not (board[cx][cy] or board[cx+1][cy] or board[cx][cy-1] or board[cx+1][cy-1])

 

 

정답 코드

from collections import deque

def solution(board):
    N = len(board)
    queue = deque([(0, 0, False, 0)]) #x좌표, y좌표, 가로(False)-세로(True), count
    
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    seen = dict()
    
    while queue :
        pop_ = queue.popleft()
        cx, cy, is_portrait, cnt = pop_
        
        if (cx, cy, is_portrait) not in seen :
            seen[(cx, cy, is_portrait)] = cnt
        else :
            if seen[(cx, cy, is_portrait)] > cnt :
                seen[(cx, cy, is_portrait)] = cnt
            else :
                continue

        if (cx, cy) == (N-1, N-1) or (cx+is_portrait, cy+(not(is_portrait))) == (N-1, N-1) :
            break
                
        for i in range(4) :
            nx = cx + dx[i]
            ny = cy + dy[i]
            
            # 이동해서 queue에 넣기
            if 0 <= nx < N - is_portrait and 0 <= ny < N - (not(is_portrait)) :
                if not (board[nx][ny] or board[nx+is_portrait][ny+(not(is_portrait))]) :
                    queue.append((nx, ny, is_portrait, cnt+1))
            
            #회전을 위해 벽이 있는지 체크
            south_east = cx < N-1 and cy < N-1 and not (board[cx][cy] or board[cx+1][cy] or board[cx][cy+1] or board[cx+1][cy+1])
            north_east = cx > 0 and cy < N-1 and not (board[cx][cy] or board[cx-1][cy] or board[cx][cy+1] or board[cx-1][cy+1])
            south_west = cx < N-1 and cy > 0 and not (board[cx][cy] or board[cx+1][cy] or board[cx][cy-1] or board[cx+1][cy-1])   
            
            # 회전해서 queue에 넣기
            if not is_portrait : #가로로 놓여있다면
                if south_east :
                    queue.append((cx, cy, not(is_portrait), cnt+1))
                    queue.append((cx, cy+1, not(is_portrait), cnt+1))

                if north_east :
                    queue.append((cx-1, cy, not(is_portrait), cnt+1))
                    queue.append((cx-1, cy+1, not(is_portrait), cnt+1))

            else : #세로로 놓여있다면 
                if south_east :
                    queue.append((cx, cy, not(is_portrait), cnt+1))
                    queue.append((cx+1, cy, not(is_portrait), cnt+1))

                if south_west :
                    queue.append((cx, cy-1, not(is_portrait), cnt+1))
                    queue.append((cx+1, cy-1, not(is_portrait), cnt+1))

    return min(seen.get((N-1, N-1, False), float('inf')), 
               seen.get((N-1, N-1, True), float('inf')),
               seen.get((N-2, N-1, True), float('inf')),
               seen.get((N-1, N-2, False), float('inf')))