[카카오 코테] 블록 이동

문제 설명

로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

입출력 예

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

입출력 예에 대한 설명

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

 

 

 

 

 

 

초기접근

---

• 움직이는 모든 경우의 수로 움직이기
• 어디로든 못 움직이는 상황일때 그 경우 끝내고 걸린시간 배열에 넣기
• 왔던 방향으로 되돌아가기 없음 -> 두 점 다 visited = 1 이면 그 방향으로 못감

이런식으로 구현할 수 있도록 내 나름대로 조건을 써보았다,

 

여기서 간과한 점이, 최단경로 구할때는 BFS가 훨씬 편한데 또 DFS로 구현하려고 해서 복잡해졌었다.

 

그리고, 다음 공간으로 이동할 수 있는지 판별하는 부분이 상당히 까다로웠다.

 

visited 확인해야하지, 4방향 이동 확인해야하지, 또 블록의 위치마다 회전하는 방향도 달라져서 경우의 수가 엄청 많았다.

 

 

 

 

 

 

 

 

답 보고 얻어낸 핵심 아이디어들

---

• 기본은 BFS로 구현해라
• visited는 set으로 담고 if x not in visited 로 검사해라
• 문제에서 주어진 리스트의 주위를 1로 감싸라.
• queue에 두 점을 동시에 담아라

 

 

 

구현시 가장 어려웠던 부분

---

블록의 위치별로 회전가능한 방향들을 검사하는 부분이 가장 어려웠다.

 

쌩으로 코딩하려니까 변수들도 복잡해지고 지금 어느부분을 구현하려는지 상당히 헷갈렸다.

 

회전부분을 최종적으로 구현하기 편하게 정리를 해보자면

 

• 두 점의 x 좌표가 같으면 블록은 가로로 놓여져 있음. (y좌표 같으면 세로)
• 위, 아래로 90도 회전할때 필요한 변수는 -1, 1임. for i in [-1, 1]로 구현 가능하다
• 90도 회전시킨다고 생각하지 말고 옮기기전과 옮긴 후의 모양을 보고 어떻게 달라지는지 생각해봐라
  (1, 1), (1, 2) 이렇게 놓여져 있다고 생각하면, 아래로 회전시킨다고 가정했을때 (1, 1), (2, 1) 로 변한다.
  결국 (x1, y1), (x2, y2) -> (x1, y1), (x1+1, y1) 으로 변한다!!

 

 

 

 

정답 코드

---

from collections import deque

def display(board):
    for i in range(len(board)):
        for j in range(len(board)):
            print(board[i][j], end=' ')
        print()


def get_next(st, n_b):

    get = []
    dir = [[0, -1], [0, 1], [1, 0], [-1, 0]]

    st = list(st)
    now_x1, now_y1, now_x2, now_y2 = st[0][0], st[0][1], st[1][0], st[1][1]

    for d in dir:
        next_x1 = now_x1+d[0]
        next_y1 = now_y1+d[1]
        next_x2 = now_x2+d[0]
        next_y2 = now_y2+d[1]

        if n_b[next_x1][next_y1] == 0 and n_b[next_x2][next_y2] == 0:
            get.append({(next_x1, next_y1), (next_x2, next_y2)})

    # 막대가 가로
    if now_x1 == now_x2:
        # 위, 아래
        for i in [-1, 1]:
            if n_b[now_x1 + i][now_y1] == 0 and n_b[now_x2 + i][now_y2] == 0:
                get.append({(now_x1, now_y1), (now_x1+i, now_y1)})
                get.append({(now_x2, now_y2), (now_x2+i, now_y2)})
    elif now_y1 == now_y2:
        # 오른쪽, 왼쪽
        for i in [-1, 1]:
            if n_b[now_x1][now_y1+i] == 0 and n_b[now_x2][now_y2+i] == 0:
                get.append({(now_x2, now_y2), (now_x2, now_y2+i)})
                get.append({(now_x1, now_y1), (now_x1, now_y1+i)})
    return get





def solution(board):
    n = len(board)

    new_board = [[0] * (n+2) for _ in range(n+2)]

    for i in range(n+2):
        for j in range(n+2):
            if i == 0 or i == n+1 or j == 0 or j == n+1:
                new_board[i][j] = 1
            else:
                new_board[i][j] = board[i-1][j-1]


    start = {(1, 1), (1, 2)}
    visited = []

    queue = deque()
    queue.append((start, 0))
    visited.append(start)

    while queue:
        start, count = queue.popleft()
        if (n, n) in start:
            return count

        for next in get_next(start, new_board):
            if next not in visited:
                queue.append((next, count+1))
                visited.append(next)