리코쳇 로봇
https://school.programmers.co.kr/learn/courses/30/lessons/169199
문제
해당 문제에서 주의해야 할 사항은 한 칸씩 이동하는 것이 아니라 D(장애물) 직전 까지 가거나 맨 끝까지 가는 것이 한 번 움직이는 것이다.
풀이(BFS - deque)
-
R의 위치를 찾는다.
-
BFS 종료조건을 명시한다.
q가 비어있을 때 종료한다. -
BFS 시작 준비를 한다.
cnt는 이동 횟수이다. 처음 시작할 때에는 0이고 q에 넣어질 때마다 1 증가한다. 또한 방문처리를 해야지 무한루프가 발생하지 않는다.(갔던 곳 또 갈 수 있음)
direction은 상,하,좌,우를 나타내기 위해 다음과 같이 초기화한다. -
현재 위치가 목표지점(G)일 때 이동 횟수 최소값을 비교한다.
-
현재 포지션(cur_row, cur_col)에서 상, 하, 좌, 우 4가지 방향으로 갔을 때 새로운 포지션(new_row, new_col)값을 구한다.
새로운 포지션을 찾을 때 멈추어야 할 조건이 있다. 장애물이 있을 때, 맨 끝까지 갔을 때이다. 이 때를 기준으로 새로운 포지션을 지정하고 그 해당 포지션이 방문하지 않았으면 q에 넣는다.
from collections import deque
def solution(board):
row, col, visited = 0, 0, [[False for i in range(len(board[0]))] for j in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == "R":
row, col = i, j
break
answer = float("inf")
def bfs():
q = deque()
q.append((0, row, col))
nonlocal answer
while True:
if not q: #q가 비어있다면 종료
break
cnt, cur_row, cur_col = q.popleft() ## 이동횟수, 현재위치
visited[cur_row][cur_col] = True ## 현재 위치 방문처리
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]] ##상하좌우
if board[cur_row][cur_col] == "G": #목표지점까지 오면 cnt최소값 구하기
answer = min(answer, cnt)
continue
for arr in direction: ## 상하좌우 new_row, new_col 계산하기
new_row, new_col = cur_row, cur_col
while True:
new_row, new_col = new_row + arr[0], new_col + arr[1]
if new_row < 0 or new_row > len(board) - 1 or new_col < 0 or new_col > len(board[0]) -1 or board[new_row][new_col] == "D":
new_row, new_col = new_row - arr[0], new_col - arr[1]
break
if not visited[new_row][new_col]:
q.append((cnt + 1, new_row, new_col))
bfs()
if answer == float("inf"):
return -1
return answer결과
풀이(BFS - heapq)
deque로 할 경우 모든 경우를 탐색한다. 하지만 heapq를 사용하면 queue안에서 이동거리가 최소인 것 먼저 계산하게 되므로 최적화 된 코드가 된다.
바뀐 부분
-
import 부분(전)
(후)
-
append부분(전)
(후)
- 목표지점 도달했을 때(전)
(후)
heapq는 cnt(이동거리)기준으로 정렬되기 때문에 가장 cnt가 낮을 때 이므로 break해준다.
- pop부분(전)
(후)
from heapq import heappush, heappop
def solution(board):
row, col, visited = 0, 0, [[False for i in range(len(board[0]))] for j in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == "R":
row, col = i, j
break
answer = float("inf")
def bfs():
q = []
heappush(q, (0, row, col))
nonlocal answer
while True:
if not q: #q가 비어있다면 종료
break
cnt, cur_row, cur_col = heappop(q) ## 이동횟수, 현재위치
visited[cur_row][cur_col] = True ## 현재 위치 방문처리
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]] ##상하좌우
if board[cur_row][cur_col] == "G": #목표지점까지 오면 cnt최소값 구하기
answer = min(answer, cnt)
break
for arr in direction: ## 상하좌우 new_row, new_col 계산하기
new_row, new_col = cur_row, cur_col
while True:
new_row, new_col = new_row + arr[0], new_col + arr[1]
if new_row < 0 or new_row > len(board) - 1 or new_col < 0 or new_col > len(board[0]) -1 or board[new_row][new_col] == "D":
new_row, new_col = new_row - arr[0], new_col - arr[1]
break
if not visited[new_row][new_col]:
heappush(q, (cnt + 1, new_row, new_col))
bfs()
if answer == float("inf"):
return -1
return answer
결과
deque보다 확연히 빨라진 것을 볼 수 있다.
