블록 이동하기 - 2020 카카오 공채 (python)

프로그래머스, 2020 카카오 공채 코딩테스트 기출 - 블록 이동하기 LV3
https://programmers.co.kr/learn/courses/30/lessons/60063
BFS, 회전처리가 까다로운 문제

👀 깃헙 소스

0과 1로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

입출력 예

board			result
[[0, 0, 0, 1, 1],	7
 [0, 0, 0, 1, 0],
 [0, 1, 0, 1, 1],
 [1, 1, 0, 0, 1],
 [0, 0, 0, 0, 0]]

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

솔루션
BFS 탐색으로 que를 사용하여 이동/회전 할수 있는 경우를
can_move에 저장하고 confirm으로 방문했던 경우인지 확인한다.
방문하지 않았다면 넣을 때 이동수를 count를 1씩 추가해서 큐에 넣어준다. cur1이나 cur2가 (N,N)일 때 count를 return 한다.
회전하는 경우 가로방향일때는 위/아래에 1이 하나라도 있으면 해당 방향 회전이 불가능하고, 세로방향일때는 왼쪽/오른쪽에 1이 하나라도 있으면 해당 방향 회전이 불가능하다는 것을 이용하여 푼다.

# board 외벽으로 둘러싼 후 new_board로 예외 처리
[[1, 1, 1, 1, 1, 1, 1],
 [1, 0, 0, 0, 1, 1, 1], 
 [1, 0, 0, 0, 1, 0, 1], 
 [1, 0, 1, 0, 1, 1, 1], 
 [1, 1, 1, 0, 0, 1, 1], 
 [1, 0, 0, 0, 0, 0, 1], 
 [1, 1, 1, 1, 1, 1, 1]]

코드

# 파이썬
from collections import deque

def can_move(cur1, cur2, new_board):
    Y, X = 0, 1
    cand = []
    # 평행이동
    DELTAS = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    for dy, dx in DELTAS:
        nxt1 = (cur1[Y] + dy, cur1[X] + dx)
        nxt2 = (cur2[Y] + dy, cur2[X] + dx)
        if new_board[nxt1[Y]][nxt1[X]] == 0 and new_board[nxt2[Y]][nxt2[X]] == 0:
            cand.append((nxt1, nxt2))
    # 회전
    if cur1[Y] == cur2[Y]: # 가로방향 일 때
        UP, DOWN = -1, 1
        for d in [UP, DOWN]:
            if new_board[cur1[Y]+d][cur1[X]] == 0 and new_board[cur2[Y]+d][cur2[X]] == 0:
                cand.append((cur1, (cur1[Y]+d, cur1[X])))
                cand.append((cur2, (cur2[Y]+d, cur2[X])))
    else: # 세로 방향 일 때
        LEFT, RIGHT = -1, 1
        for d in [LEFT, RIGHT]:
            if new_board[cur1[Y]][cur1[X]+d] == 0 and new_board[cur2[Y]][cur2[X]+d] == 0:
                cand.append(((cur1[Y], cur1[X]+d), cur1))
                cand.append(((cur2[Y], cur2[X]+d), cur2))
                
    return cand

def solution(board):
    # board 외벽 둘러싸기
    N = len(board)
    new_board = [[1] * (N+2) for _ in range(N+2)]
    for i in range(N):
        for j in range(N):
            new_board[i+1][j+1] = board[i][j]

    # 현재 좌표 위치 큐 삽입, 확인용 set
    que = deque([((1, 1), (1, 2), 0)])
    confirm = set([((1, 1), (1, 2))])

    while que:
        cur1, cur2, count = que.popleft()
        if cur1 == (N, N) or cur2 == (N, N):
            return count
        for nxt in can_move(cur1, cur2, new_board):
            if nxt not in confirm:
                que.append((*nxt, count+1))
                confirm.add(nxt)

주의 :
이 문제는 좌표가 두개이고 회전처리가 까다워 난이도가 높은 편이다.
회전하는 경우를 가로방향일때와 세로방향일때가 나눠서 풀어주어야 한다.