리코쳇 로봇

https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

I. 문제 개요

 

BFS를 활용하여 최단 경로를 찾는 것이 문제의 목표이다.

 

하지만, 여기서는 로봇이 장애물 또는 경계에 부딪힐 때 까지 움직인다는 점에 주의해야 한다.

 

로봇이 한번에 한 칸씩 움직이는 상황이 아니다.

 

II. 알고리즘 및 풀이

1. 초기화 및 탐색준비

# 1. 초기화 및 탐색준비
ans = -1
n, m = len(board), len(board[0])

que = deque()
dist = [[10**6] * m for _ in range(n)]

for i in range(n):
    for j in range(m):
        if board[i][j] == 'R':
            que.append([i, j, 0])
            break

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

 

변수 dist는 칸 별에 도착하기 위해 필요한 최소 이동횟수를 저장하는 2D list이다.

 

주어진 board에서 시작위치를 찾고, deque에 넣어준다.

 

dx, dy는 차례대로 상, 하, 좌, 우로 이동하는데 사용하는 변위값이다.

 

2. BFS 탐색

# 2. BFS 탐색
while que:
	# 1) 현재 칸에 대한 정보 회수
    x, y, dst = que.popleft()
	
    # 2) 목표지점 도달여부 판정
    if board[x][y] == 'G':
        ans = dst
        break
	
    # 3) 상, 하, 좌, 우 탐색
    for i in range(4):
        nx, ny = x, y

        while (0 <= nx + dx[i] < n) and (0 <= ny + dy[i] < m) and (board[nx+dx[i]][ny+dy[i]] != 'D'):
            nx += dx[i]     # 장애물에 부딪히거나, 경계에 도달하기 까지 무조건 직진
            ny += dy[i]

        if dist[nx][ny] > dst + 1:
            dist[nx][ny] = dst + 1
            que.append([nx, ny, dst + 1])

return ans

 

1) 현재 칸에 대한 정보 회수

deque의 맨 앞에 들어있는 값을 빼온다.

 

x와 y는 현재 위치, dst는 board[x][y] 까지 오는데 필요한 이동 횟수이다

 

2) 목표지점 도달여부 판정

목표지점에 도달했다면, ans를 dst의 값으로 변경하고, 탐색을 중지한다.

 

3) 상, 하, 좌, 우 탐색

상하죄우 중 방향을 정하고, board를 벗어나거나 장애물에 닿기 직전까지 직진한다.

 

만약 현재 위치 nx, ny까지 이동한 횟수가 dist에 기록된 이동횟수보다 작다면, dist[nx][ny]에 적힌 값을 (현재까지의 이동횟수)+1로 바꾼다.

 

 

 

III. 전체 코드

from collections import deque


def solution(board):
    # 1. 초기화 및 탐색준비
    ans = -1
    n, m = len(board), len(board[0])

    que = deque()
    dist = [[10**6] * m for _ in range(n)]

    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                que.append([i, j, 0])
                break

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    # 2. BFS 탐색
    while que:
        # 1) 현재 칸에 대한 정보 회수
        x, y, dst = que.popleft()

        # 2) 목표지점 도달여부 판정
        if board[x][y] == 'G':
            ans = dst
            break

        # 3) 상, 하, 좌, 우 탐색
        for i in range(4):
            nx, ny = x, y

            while (0 <= nx + dx[i] < n) and (0 <= ny + dy[i] < m) and (board[nx+dx[i]][ny+dy[i]] != 'D'):
                nx += dx[i]     # 장애물에 부딪히거나, 경계에 도달하기 까지 무조건 직진
                ny += dy[i]

            if dist[nx][ny] > dst + 1:
                dist[nx][ny] = dst + 1
                que.append([nx, ny, dst + 1])

    return ans

 

IV. 풀이 결과

 

V. 참고 사이트

https://evga7.tistory.com/129