프로그래머스 블록 이동하기 (파이썬)

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

코딩테스트 연습 - 블록 이동하기 | 프로그래머스

1. 로봇이 있는 처음 두 칸의 좌표 [[0, 0], [0, 1]]을 큐에 넣고 bfs를 실행한다

2. 방문했는지 체크하는 배열에도 위와 같은 형식으로 두 개의 좌표를 묶어서 넣어준다

3. 현재 큐의 길이만큼 실행한다. 이렇게해야 현재 좌표에서 가능한 모든 이동, 회전을 하고 cnt를 증가할 수 있다

4. 각 좌표가 dx, dy에 따라 이동할 수 있는지 검증한다.

5. 두 좌표의 x축이 같고 아래나 위로 이동할 수 있다면 세로 형태로 회전할 수 있으므로 turn 함수 실행

   두 좌표의 y축이 같고 좌우로 이동할 수 있다면 가로 형태로 회전할 수 있으므로 turn 함수 실행

6. 회전할 때는 각 좌표를 축으로 회전하는 2가지 경우를 다 고려한다.

7. 두 좌표를 정렬한 후 방문한 적이 없는 두 좌표라면 q와 c에 저장한다. 

   정렬해서 [[0, 0], [0, 1]] [[1,0], [0, 0]] 처럼 중복되는 케이스를 배제했다.

8. [m-1, n-1] 좌표에 도착했다면 cnt 변수를 return 한다

from collections import deque

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

q = deque()
c = []

def bfs(r, b, m, n):
    q.append(r)
    c.append(r)
    cnt = 0
    while q:
        qlen = len(q)
        while qlen:
            x = q.popleft()
            if x == [[m-1, n-2], [m-1, n-1]] or x == [[m-2, n-1], [m-1, n-1]]:
                return cnt
            for i in range(4):
                temp = []
                flag = 0
                for j in range(2):
                    nx = x[j][0] + dx[i]
                    ny = x[j][1] + dy[i]
                    if 0 <= nx < m and 0 <= ny < n and b[nx][ny] == 0:
                        temp.append([nx, ny])
                    else:
                        flag = 1
                        break
                if not flag:
                    if x[0][0] == x[1][0]:
                        if i == 0 or i == 1:
                            turn(x, i, '|')
                    elif x[0][1] == x[1][1]:
                        if i == 2 or i == 3:
                            turn(x, i, '-')
                    temp.sort()
                    if temp not in c:
                        q.append(temp)
                        c.append(temp)
            qlen -= 1
        cnt += 1

def turn(x, i, mode):
    if mode == '|':
        for j in range(2):
            nx = x[j]
            ny = [x[j][0] + dx[i], x[j][1]]
            temp = [nx, ny]
            temp.sort()
            if temp not in c:
                q.append(temp)
                c.append(temp)

    elif mode == '-':
        for j in range(2):
            nx = [x[j][0], x[j][1] + dy[i]]
            ny = x[j]
            temp = [nx, ny]
            temp.sort()
            if temp not in c:
                q.append(temp)
                c.append(temp)

def solution(board):
    m, n = len(board), len(board[0])
    robot = [[0, 0], [0, 1]]
    return(bfs(robot, board, m, n))