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 함수를 완성해주세요.
지도 탐색 문제는 DFS/BFS로 문제를 풀수 있으며 특히 이번 문제의 경우 로봇은 한칸씩 움직이므로 대표적인 BFS문제가 됩니다.
정말 BFS…. 보면 볼수록 신기한거 같아요
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from collections import deque
def solution(board):
#맵의 외곽에 벽을 두는 형태로 맵 변형
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) 수행
q = deque()
visited =[]
pos = {(1,1),(1,2)} #시작위치 설정
q.append((pos, 0)) #큐에 삽입한 뒤에
visited.append(pos) #방문처리
#큐가 빌 때까지 반복
while q:
pos, cost = q.popleft()
#(n,n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환
if (n,n) in pos:
return cost
#현재 위치에서 이동할 수 있는 위치 확인
for next_pos in get_next_pos(pos, new_board):
#아직 방문하지 않은 위치라면 큐에 삽입하고 방문처리
if next_pos not in visited:
q.append((next_pos, cost + 1))
visited.append(next_pos)
return 0
일단 시작하는 로봇의 위치는 (1,1)이고 도착해야하는 위치는 (N,N)으로 고정이 되어 있습니다. 즉 지도의 정보만 입력을 받게 됩니다.
지도를 입력받을때 보통 이런 문제의 경우 맵의 끝부분을 그냥 갈 수 없는 곳으로 처리하기 보다 벽을 둘러서 못가게 명시적으로 표시해두는 것이 문제 풀이에 도움이 된다고 합니다. 보는 것 처럼 새로 입력 받는 보드는 n+2로 상하좌우 한칸씩 클렸다고 보시면 됩니다.
그리고 입력받을때는 +1을 해서 맵의 정중앙이니 결과적으로 맵 밖에 한칸씩 벽이 둘러졌다고 보시면 됩니다.
그다음 현재 이동할 위치를 관리할 q와 방문을 했는지 확인하기 위한 visited를 선언을 합시다.
로봇의 첫 위치는 (1,1) (1,2)로 고정이 되어있습니다. 이를 설정을 해줍시다. 그리고 q에다가 해당 위치를 삽입하고 여기까지 도달하는데 얼마가 걸렸는지 cost비용을 계산해줍시다. 초기화된 위치는 바로 있을 수 있으니 0이 들어갑니다. 이제 while문 즉 이동을 관리하는 q가 완전히 빌때까지 계산을 수행합시다.
1
2
3
4
5
6
7
8
9
10
11
while q:
pos, cost = q.popleft()
#(n,n) 위치에 로봇이 도달했다면, 최단 거리이므로 반환
if (n,n) in pos:
return cost
#현재 위치에서 이동할 수 있는 위치 확인
for next_pos in get_next_pos(pos, new_board):
#아직 방문하지 않은 위치라면 큐에 삽입하고 방문처리
if next_pos not in visited:
q.append((next_pos, cost + 1))
visited.append(next_pos)
q는 위치와 비용을 관리한다고 했습니다. pos와 cost로 받아줍시다.
그리고 pos가 만약 n,n 끝지점에 도달을 했다면 비용을 반환하는 것으로 종료합니다. n,n지점으로 갈 수 없는 경우는 고려하지 않기 때문입니다. 이를 고려했다면 예외적인 처리를 해야하는데 무조건 갈 수 있으니 cost 비용을 반환하는 것으로 마무리를 할 수 있습니다.
이제 for문을 살펴 봅시다.
next_pos는 get_next_pos의 함수에서 반환한 리스트를 순회하게 됩니다. 그렇다면 get_next_pos 함수를 봅시다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
pos1_next_x, pos1_next_y, pos2_next_x, pos2_next_y = pos1_x + dx[i], pos1_y + dy[i], pos2_x + dx[i], pos2_y + dy[i]
#이동하고자 하는 두 칸이 모두 비어 있다면
if board[pos1_next_x][pos1_next_y] == 0 and board[pos2_next_x][pos2_next_y] == 0:
next_pos.append({(pos1_next_x, pos1_next_y), (pos2_next_x, pos2_next_y)})
#현재 로봇이 가로로 놓여 있는 경우
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)})
#현재 로봇이 세로로 놓여 있는 경우
elif 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
next_pos 반환결과(이동이 가능한 위치)를 담을 리스트를 선언을 합시다.
처음에 pos는 집합으로 관리를 했습니다. 이 이유는 순서에 구애받지 않기 위한것인데 로봇의 위치가 (1,2) (1,1) 이건 (1,1) (1,2)이건 고려할 대상이 아니지만 리스트로 받게 된다면 위치에 따라서 다른 결과가 나올 수 있기 때문에 이를 집합(set)으로 관리하여 동일한 노드인지만 체크하면 됬습니다
다만 이렇게 하면 연산할때 불편하니 다시 리스트로 바꾸게 됩니다.
이제 로봇은 일단 4위치(상하좌우) 이동이 가능합니다. 그리고 이동하는 두 칸이 모두 비어 있다면 로봇이 이동가능하다는 의미이니 next_pos에 추가를 해서 표시를 해줍니다.
그리고 로봇의 상태는 두가지 입니다. 가로로 놓여있거나 세로로 놓여 있는 경우 입니다.
첫번째 로봇이 가로로 놓인 상태를 봅시다.
1
2
3
4
5
6
7
#현재 로봇이 가로로 놓여 있는 경우
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)})
로봇이 두칸을 차지하는데 이 두칸의 x값이 같다면 가로로 놓여 있는 상태임을 유추 할 수 있습니다.
이 상태에서 위쪽으로 회전하거나 아래쪽으로 회전할 수 있다면 확인을 하고 next_pos에 추가를 해줍시다.
1
2
3
4
5
6
7
#현재 로봇이 세로로 놓여 있는 경우
elif 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)})
두칸의 y값이 같다면 로봇은 세로로 놓여 있는 상태입니다. 이때 왼쪽으로 회전하거나 오른쪽으로 회전하는지 체크를 하고 가능하다면 마찬가지로 next_pos에 추가를 해줍시다.
이제 다시 솔루션으로 가봅시다.
1
2
3
4
5
for next_pos in get_next_pos(pos, new_board):
#아직 방문하지 않은 위치라면 큐에 삽입하고 방문처리
if next_pos not in visited:
q.append((next_pos, cost + 1))
visited.append(next_pos)
get_next_pos를 통해서 모든 갈 수 있는 곳을 체크를 하고 방문을 하지 않았다면 q에다가 추가를 하고 cost를 관리를 하고 visited에 추가를 합니다.
이렇게하면 자연스럽게 다음으로 갈 수 있는 모든 구간(BFS)체크가 이루어지게 되고
n,n에 도달하는 방법은 여러가지가 있겠지만 가장먼저 조건을 만족하는 녀석이 제일 짧은 녀석인 것도 확인 할 수 있습니다. visited를 통해서 한번 갔던 곳은 또 가지 않으니 쭉 직진하기 때문입니다.
Comments powered by Disqus.