[프로그래머스(Programmers)/ Level3] 블록 이동하기 (파이썬, Python3)

문제

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 함수를 완성해주세요.

 

---

제한사항

• 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초가 걸립니다.

 

---

문제 풀이

 

로봇을 (N, N) 위치에 최소 경로로 이동시키기 위해 BFS 알고리즘을 사용했지만 이 문제는 기본적으로 로봇의 이동, 회전의 구현하는 것이 관건이었습니다. 게다가 로봇은 두 좌표를 차지해서 구현하는데 꽤나 까다로웠네요.. ㅎ 먼저 어떤 경우에 로봇을 이동, 회전할 수 있는지 알아보겠습니다.

 

이동은 상하좌우로만 가능하기 때문에 이동하기 위한 반경은 위와 같습니다. 만약 위의 반경의 지도 값이 모두 0이면

 

위와 같이 상하좌우로 모두 이동할 수 있습니다. 

만약 위와 같이 위에 벽이 있으면 위로 이동할 수 없습니다. 이해 되셨죠?? 이번엔 회전에 대해서 보겠습니다. 

 

회전의 반경은 위와 같습니다.

반경은 위와 같습니다.

만약 위와 같이 위에 한 곳이라도 벽이 있으면 로봇은 위의 어떤 방향으로도 회전할 수 없습니다!

 

이동, 회전을 BFS 알고리즘에 적용하여 로봇을 움직이기 위해 한 가지 작업이 필요합니다. 로봇이 지도 범위에서 벗어나지 않도록 지도를 원래 크기 + 2 만큼 증가시킨 후 모서리를 전부 1로 채우는 작업입니다. 

이제 BFS 알고리즘을 적용하여 이동, 회전을 시켜봅니다!

 

2022.07.14 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

[파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

 

1) 시작 좌표 (1, 1), (1, 2) 와 거리 값을 튜플 형태 ((1, 1), (1, 2), 0)로 deque에 넣고, 좌표값들을 set에 넣는다(이미 간 좌표는 가지 않기 위해).

2) 좌표를 deque에서 pop하고, pop으로 얻은 좌표의 상하좌우 이동 가능 좌표와 회전 가능 좌표를 구하여 이미 방문한 좌표인지 set을 통해 확인하고 방문한 좌표가 아니면 거리 값 + 1을 한 후 deque에 넣는다.

3) 기본적으로 deque에 데이터가 없을 때 까지 위 과정을 반복하고 pop으로 얻은 좌표에서 둘 중 한 좌표라도 (N, N) 좌표에 도달하면 이때의 거리 값을 결괏값으로 반환하고 종료한다. 

---

구현

 

코드

from collections import deque

def solution(board):
    # 상하좌우 인덱스
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    lenb = len(board)
    # 외벽 생성
    nboard = [[1] * (lenb+2) for _ in range(lenb+2)]
    for i in range(lenb):
        for j in range(lenb):
            nboard[i+1][j+1] = board[i][j]
    # BFS 적용하기 위한 deque
    dq = deque([((1, 1), (1, 2), 0)])
    # 방문한적 있는 좌표인지 확인하기 위한 set
    ch_set = set([((1, 1), (1, 2))])
    while dq:
        s1, s2, dis = dq.popleft()
        # N x N에 도달하면 종료
        if s1 == (lenb, lenb) or s2 == (lenb, lenb):
            return dis
        tmp = []
        # 상하좌우 이동
        for i in range(4):
            s1_i = s1[0] + dx[i]
            s1_j = s1[1] + dy[i]
            s2_i = s2[0] + dx[i]
            s2_j = s2[1] + dy[i]
            if nboard[s1_i][s1_j] == 0 and nboard[s2_i][s2_j] == 0:
                tmp.append(((s1_i, s1_j), (s2_i, s2_j)))   
        # 수평 -> 수직
        if s1[0] == s2[0]:
            # 위로 회전, 아래로 회전
            for i in [1, -1]:
                if nboard[s1[0] + i][s1[1]] == 0 and nboard[s2[0] + i][s2[1]] == 0:
                    tmp.append((s1, (s1[0] + i, s1[1])))
                    tmp.append((s2, (s2[0] + i, s2[1])))
        # 수직 -> 수평
        else:
            # 오른쪽으로 회전, 왼쪽으로 회전
            for i in [1, -1]:
                if nboard[s1[0]][s1[1] + i] == 0 and nboard[s2[0]][s2[1] + i] == 0:
                    tmp.append(((s1[0], s1[1] + i), s1))
                    tmp.append(((s2[0], s2[1] + i), s2))   
        for pset in tmp:
            # ch_set에 해당 좌표가 없으면 dq에 추가
            if pset not in ch_set:
                dq.append((*pset, dis + 1))
                ch_set.add(pset)

 

결과