[Python] 블록이동하기
Programmers : 블록이동하기
문제 설명
로봇개발자 “무지”는 한 달 앞으로 다가온 “카카오배 로봇경진대회”에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
입출력 예
입출력 예에 대한 설명
문제에 주어진 예시와 같습니다. 로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.
풀이
먼저, 너비우선탐색에 대해서 알아보겠습니다.
- 그래프에서 가까운 노드부터 탐색하는 알고리즘으로 큐 자료구조를 이용합니다.
- 알고리즘의 진행 순서는 다음과 같습니다.
- 1) 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
- 2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드들을 큐에 삽입하고 방문처리
- 3) 2번의 과정을 더 이상 반복할 수 없을 때까지 반복
- 너비 우선 탐색은 가까운 노드부터 탐색하므로, 모든 간선의 비용이 1인 그래프에서 BFS를 사용하면 최단 거리를 계산할 수 있습니다.
너비우선탬색(bfs)를 이용해 로봇이 마지막 위치까지 도달하는 최단 시간을 구해보겠습니다.
1) `board` 주변에 벽을 칩니다(=1)
2) 큐에 시작 위치 및 소요시간(=0) 삽입합니다.
- 현재 로봇의 위치를 집합으로 관리할 수 있습니다. {(1,1),(1,2)}과 {(1,2),(1,1)}은 같습니다.
3) 큐의 맨 앞에서 하나를 추출하고 갈 수 있는 방향 목록을 다시 큐에 넣어줍니다.
- 큐에 넣을때 소요시간을 1씩 더해줍니다.
- 방문했던 위치였다면 제외합니다.
4) 3)을 계속 반복하다가 로봇의 위치가 `(n,n)`이 되면 return합니다.
5) 최종 소요시간을 출력합니다.
현재 로봇의 위치를 받고 갈 수 있는 방향을 출력하는 함수를 생성하는 일이 까다로웠습니다. 로봇은 상하좌우 뿐만 아니라 시계방향 반시계방향으로 회전할 수 있습니다. next_pos라는 빈 리스트를 선언해주고 갈 수 있는 방향을 하나하나씩 넣어보겠습니다.
상하좌우
4가지 방향으로 움직일 수 있을 것이며, 움직일 방향의 좌표값이 1이 아니면 됩니다. 따라서 4가지 방향 모두를 체크하며 좌표값이 1이 아니라면 next_pos에 넣어줍니다.
다음으로 회전의 경우는 로봇이 가로로 놓인 경우와 세로로 놓인 경우로 생각해볼 수 있습니다.
가로로 놓인 경우
위의 2개의 칸을 확인합니다. 하나라고 1이라면 회전이 불가능하므로 둘다 0 인경우에만 회전한 후의 위치를
next_pos에 넣어줍니다.아래의 2개의 칸을 확인합니다. 마찬가지로 하나라도 1이면 회전이 불가능하므로 둘다 0인 경우에만 회전한 후의 위치를
next_pos에 넣어줍니다.
세로로 놓인 경우
- 왼쪽의 2개의 칸을 확인합니다. 둘다 0인 경우에만 회전한 후의 위치를
next_pos에 넣어줍니다. - 오른쪽의 2개의 칸을 확인합니다. 둘다 0인 경우에만 회전한 후의 위치를
next_pos에 넣어줍니다.
from collections import deque
def get_next_pos(pos, board):
next_pos = []
pos = list(pos)
pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
# 상하좌우
dx = [0,0,-1,1]
dy = [1,-1,0,0]
for i in range(4):
if board[pos1_x + dx[i]][pos1_y + dy[i]] == 0 and board[pos2_x + dx[i]][pos2_y + dy[i]] == 0:
next_pos.append({(pos1_x+dx[i], pos1_y+dy[i]),(pos2_x+dx[i], pos2_y+dy[i])})
# 가로로 있는 경우
if pos1_x == pos2_x:
for i in [-1, 1]: # 위, 아래를 확인해야함
if board[pos1_x+i][pos1_y] == 0 and board[pos2_x+i][pos2_y] == 0:
next_pos.append({(pos1_x, pos1_y),(pos1_x+i, pos1_y)})
next_pos.append({(pos2_x, pos2_y),(pos2_x+i, pos2_y)})
if pos1_y == pos2_y:
for i in [-1, 1]: # 왼쪽, 오른쪽을 확인해야함
if board[pos1_x][pos1_y+i] == 0 and board[pos2_x][pos2_y+i] == 0:
next_pos.append({(pos1_x, pos1_y),(pos1_x, pos1_y+i)})
next_pos.append({(pos2_x, pos2_y),(pos2_x, pos2_y+i)})
return next_pos
def solution(board):
# 맵의 외곽에 1로 벽을 생성한다.
n = len(board)
new_board = [[1]*(n+2) for _ in range(n+2)]
for i in range(n):
for j in range(n):
new_board[i+1][j+1] = board[i][j]
# bfs 수행
queue = deque()
visited = []
start_point = {(1,1),(1,2)} # 패딩으로 인해 start point도 변한다.
queue.append((start_point,0)) # 큐에 삽입
visited.append(start_point) # 방문 처리
while queue:
pos, count = queue.popleft()
# n,n에 위치했다면 최단 거리이므로 return
if (n,n) in pos:
return count
# 현재 위치에서 이동할 수 있는 위치 확인
for next_pos in get_next_pos(pos, new_board):
# 아직 방문하지 않은 위치라면 큐에 삽입하고 방문 처리
if next_pos not in visited:
queue.append((next_pos, count+1))
visited.append(next_pos)
