[프로그래머스] 블록 이동하기 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/60063

프로그래머스

---

'''

    Chapter 13. 블록 이동하기

    접근법 1

        이동가능한 방법 12가지

        1. 상하좌우 4가지

        2. 가로로 되었을 때 아래쪽으로 회전 2가지, 위쪽으로 회전 2가지

        3. 세로로 되었을 때 오른쪽으로 회전 2가지, 왼쪽으로 회전 2가지

        경우 3가지로 나눠서 구현하기

        로봇이 2칸을 차지하니 방문 표시를 visited = []로 하기

        계속 시간초과가 나서 로봇의 위치를 list -> set

        -----------------------------------------------

        in 연산자

            list, tuple

                Average: O(n)

                하나하나 순회하기 때문에 데이터의 크기만큼 시간 복잡도를 갖게 됩니다.

            set, dictionary

                Average: O(1), Worst: O(n)

                내부적으로 hash를 통해서 자료들을 저장하기 때문에 시간복잡도가 O(1)가 가능하고 O(n)의 경우에는 해시가 성능이 떨어졌을(충돌이 많은 경우) 때 발생합니다.

'''

from collections import deque

# 현 위치에서 이동 가능 한 곳 찾기
def find_position(current_position,board):
    # 이동 가능한 곳
    next_position = []
    
    # 현 위치
    current_position = list(current_position)
    one_r, one_c = current_position[0]
    two_r, two_c = current_position[1]

    # 1. 상하좌우 이동
    for dr,dc in [[-1,0],[1,0],[0,-1],[0,1]]:
        one_next_r, one_next_c, two_next_r, two_next_c = one_r+dr, one_c+dc, two_r+dr, two_c+dc
        # 이동 가능?
        if board[one_next_r][one_next_c] == 0 and board[two_next_r][two_next_c] == 0:
            next_position.append({(one_next_r, one_next_c), (two_next_r, two_next_c)})
    
    # 2. 로봇이 가로로 놓여 있다.
    if one_r == two_r:
        # 2-1. 아래로 회전(아래 두 칸 다 0이어야함), 위로 회전(위 두 칸 다 0이어야함)
        for i in [1,-1]:
            # 이동 가능?
            if board[one_r+i][one_c] == 0 and board[two_r+i][two_c] == 0:
                next_position.append({(one_r, one_c), (one_r+i, one_c)})
                next_position.append({(two_r, two_c), (two_r+i, two_c)})
    
    # 3. 로봇이 세로로 놓여 있다.
    elif one_c == two_c:
        # 3-1. 왼쪾 회전(왼쪽 두 칸 다 0이어야함), 오른쪽으로 회전(오른쪽 두 칸 다 0이어야함)
        for i in [1,-1]:
            # 이동 가능?
            if board[one_r][one_c+i] == 0 and board[two_r][two_c+i] == 0:
                next_position.append({(one_r, one_c), (one_r, one_c+i)})
                next_position.append({(two_r, two_c), (two_r, two_c+i)})
    
    # 4. 이동 가능한 모든 위치 리스트
    return next_position
                
def solution(board):
    answer = 0
    N = len(board)
    board = [[1]*(N+2)] + [[1]+b+[1] for b in board] + [[1]*(N+2)]
    
    que = deque()
    # 방문 표시
    visited = []
    
    # 시작 위치 
    start_position = {(1,1),(1,2)}
    # ([(one_r,one_c),(two_r,two_c)],cnt)
    que.append((start_position, 0))
    visited.append(start_position)
    
    while que:
        # 현 위치, 거리
        current_position, cnt = que.popleft()
        # (N,N)에 도착?
        if (N,N) in current_position:
            return cnt
            
        # 이동 가능한 위치들
        next_position = find_position(current_position,board)
        # 이동
        for position in next_position:
            # 방문한 적 없는 위치
            if position not in visited:
                # 방문
                visited.append(position)
                que.append((position,cnt+1))