[프로그래머스 Level3] 블록 이동하기 - 파이썬(Python) - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

문제 설명

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분 없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초입니다.

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

 

 

 

---

한 번의 이동의 경우의 수는 최대 (상, 하, 좌, 우) 이동 + (4가지 경우의 회전)으로 8가지이다.

그리고, 회전의 경우에는 로봇이 가로로 놓여 있는지, 세로로 놓여져 있는지에 따라 어떤 방법으로 회전시켜야 하느냐가 다르다. 로봇이 가로로 놓여져 있다면 y위치를 옮겨서 회전해주어야 하고, 세로로 놓여져 있다면 x위치를 옮겨서 회전해주어야 한다.

 

처음에는 다익스트라 문제인 줄 알고 코드가 너무 복잡해질 것 같아서 막막했었는데, 알고 보니 단순 BFS로도 충분히 풀릴 수 있는 문제였다. visited에서 리스트 자료구조를 사용했더니 if-in 문에서 아마 시간초과가 났던 것 같다. 방문 여부 확인을 set 자료구조를 이용하니 해결되었다.

 

 

<< 전체 코드 >>

from collections import deque

def none_inBoard(pos, n):
    if pos < 0 or pos >= n:
        return True
    return False
    
def solution(board):
    n = len(board)
    dy = [-1, 1, 0, 0]
    dx = [0, 0, -1, 1]
    
    q = deque()
    q.append([(0, 0), (0, 1), 0])
    visited = set([((0, 0), (0, 1))])
    while q:
        pos1, pos2, cnt = q.popleft()
        y1, x1 = pos1
        y2, x2 = pos2
        if (y1, x1) == (n-1, n-1) or (y2, x2) == (n-1, n-1):
            return cnt
        for i in range(4):
            ny1, nx1 = y1 + dy[i], x1 + dx[i]
            ny2, nx2 = y2 + dy[i], x2 + dx[i]
            if none_inBoard(ny1, n) or none_inBoard(nx1, n) or none_inBoard(ny2, n) or none_inBoard(nx2, n):
                continue
            if board[ny1][nx1] == 0 and board[ny2][nx2] == 0 and ((ny1, nx1), (ny2, nx2)) not in visited:
                q.append([(ny1, nx1), (ny2, nx2), cnt + 1])
                visited.add(((ny1, nx1), (ny2, nx2)))
        if y1 == y2:
            for d in [-1, 1]:
                if none_inBoard(y1+d, n) or none_inBoard(y2+d, n) or board[y1+d][x1] == 1 or board[y2+d][x2] == 1:
                    continue
                if ((y2+d, x2), (y2, x2)) not in visited:
                    q.append([(y2+d, x2), (y2, x2), cnt + 1])
                    visited.add(((y2+d, x2), (y2, x2)))
                if ((y1+d, x1), (y1, x1)) not in visited:
                    q.append([(y1+d, x1), (y1, x1), cnt + 1])
                    visited.add(((y1+d, x1), (y1, x1)))
        else:
            for d in [-1, 1]:
                if none_inBoard(x1+d, n) or none_inBoard(x2+d, n) or board[y1][x1+d] == 1 or board[y2][x2+d] == 1:
                    continue
                if ((y2, x2+d), (y2, x2)) not in visited:
                    q.append([(y2, x2+d), (y2, x2), cnt + 1])
                    visited.add(((y2, x2+d), (y2, x2)))
                if ((y1, x1+d), (y1, x1)) not in visited:
                    q.append([(y1, x1+d), (y1, x1), cnt + 1])
                    visited.add(((y1, x1+d), (y1, x1)))