프로그래머스 리코쳇 로봇 문제는 단순한 탐색 문제가 아니라, 한 번 이동하면 장애물이나 벽에 부딪힐 때까지 계속 미끄러지는 특수한 이동 규칙을 가지고 있습니다. 이번 글에서는 BFS(너비 우선 탐색)을 활용해 문제를 풀어가는 과정을 소개합니다.
https://school.programmers.co.kr/learn/courses/30/lessons/169199
🧩 문제 이해하기
게임판(board)은 2차원 배열 형태이며, 다음과 같은 요소들이 포함됩니다.
- 'R' : 로봇의 시작 위치
- 'G' : 목표 지점
- 'D' : 장애물
- '.' : 빈 칸
로봇은 한 번 움직이면 벽이나 장애물에 부딪히기 전까지 계속 직진합니다. 목표는 최소 이동 횟수로 'G'에 도착하는 것입니다. 도달할 수 없는 경우 -1을 반환해야 합니다.
🛠️ 해결 전략
이 문제를 해결하기 위해 BFS를 사용합니다. BFS는 최단 거리 탐색에 최적화된 알고리즘이기 때문에, 목표 지점까지 도달하는 최소 이동 횟수를 보장합니다.
1️⃣ 게임판 정보 파악
- 보드를 순회하면서 'R'(시작점)과 'G'(목표점)을 찾습니다.
- 방문 여부를 기록하기 위해 visited 배열을 초기화합니다.
2️⃣ BFS 탐색 시작
- 시작 위치 (r, c)와 이동 횟수 0을 큐에 삽입합니다.
- 이후 큐에서 위치를 하나씩 꺼내며 탐색을 진행합니다.
3️⃣ 목표 지점 도달 여부 확인
- 현재 위치가 'G'라면, 이동 횟수를 반환합니다.
4️⃣ 4방향으로 이동
- 상, 하, 좌, 우 네 방향에 대해 이동을 시도합니다.
- 단순히 한 칸 이동하는 것이 아니라, 벽이나 장애물에 부딪힐 때까지 미끄러져 이동해야 합니다.
- 도착한 위치가 아직 방문하지 않은 곳이라면 visited에 표시하고 큐에 추가합니다.
5️⃣ 도달 불가능한 경우
- 큐가 빌 때까지 'G'에 도착하지 못하면 -1을 반환합니다.
🖥️ 코드 구현
from collections import deque
def solution(board):
rows = len(board)
cols = len(board[0])
for r in range(rows):
for c in range(cols):
if board[r][c] == 'R':
start_point = (r,c)
elif board[r][c] == 'G':
end_point = (r,c)
queue = deque([(start_point[0], start_point[1], 0)])
visited = [[False] * cols for _ in range(rows)]
visited[start_point[0]][start_point[1]] = True
dr = [-1,1,0,0]
dc = [0,0,-1,1]
while queue:
r, c, moves = queue.popleft()
if (r,c) == end_point:
return moves
for i in range(4):
# 현재 위치
nr, nc = r, c
while 0 <= nr + dr[i] < rows and 0 <= nc + dc[i] < cols and board[nr+dr[i]][nc+dc[i]] != 'D':
nr += dr[i]
nc += dc[i]
if not visited[nr][nc]:
visited[nr][nc] = True
queue.append((nr, nc, moves+1))
return -1