알고리즘/프로그래머스
[프로그래머스]Lv2. 리코쳇 로봇(Python)
cha_eyoon
2024. 2. 9. 12:56
https://school.programmers.co.kr/learn/courses/30/lessons/169199
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 접근
BFS로 접근 시도(검색 후 아이디어 얻음)
먼저 게임 보드에서 로봇(R)의 위치를 찾아 큐에 추가하고, 해당 위치에서부터 BFS를 시작!
현재 위치에서 네 방향으로 이동할 수 있는 경우를 찾고, 해당 방향으로 미끄러지며 이동 가능한 위치 탐색
이전에 해당 위치에 도달한 적이 없거나,
이전에 도달한 경우보다 적은 이동 횟수로 도달 가능한 경우에는 큐에 해당 위치를 추가
G에 도착한 경우에는 현재까지의 이동 횟수를 반환하고,
BFS가 종료되었지만 목표 지점에 도달하지 못한 경우에는 -1을 반환
코드
from collections import *
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
def solution(board):
answer = 0
N = len(board)
M = len(board[0])
q = deque()
dist = [[987654321 for _ in range(M)] for _ in range(N)]
# 로봇의 시작 위치(R)를 찾아 큐에 추가
for i in range(N):
for j in range(M):
if board[i][j] == 'R':
q.append((i, j, 0))
dist[i][j] = 0
if q:
break
while q:
x, y, c = q.popleft()
# G에 도달한 경우 이동 횟수 반환
if board[x][y] == 'G':
return c
# 네 방향으로 이동할 수 있는 경우 탐색
for i in range(4):
n_x = x
n_y = y
# 해당 방향으로 미끄러지며 이동 가능한 위치 계속 탐색
while 0 <= n_x + dx[i] < N and 0 <= n_y + dy[i] < M and board[n_x + dx[i]][n_y + dy[i]] != 'D':
n_x += dx[i]
n_y += dy[i]
# 이전에 해당 위치에 도달한 적이 없는 경우 or 이전에 도달한 경우보다 적은 이동 횟수로 도달 가능한 경우
if dist[n_x][n_y] > c + 1:
dist[n_x][n_y] = c + 1
q.append((n_x, n_y, c + 1))
# 목표 지점에 도착할 수 없으면 -1 반환
return -1