*문제 출처는 프로그래머스에 있습니다.

문제 제목: 리코쳇 로봇 (2단계)
문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/169199
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명

나의 풀이
from collections import deque
def solution(board):
move = [(0, 1), (1, 0), (-1, 0), (0, -1)]
boards = []
for i in board:
boards.append(list(i))
r_y, r_x, g_y, g_x = 0, 0, 0, 0
for i in range(len(boards)):
for ii in range(len(boards[0])):
if boards[i][ii] == 'R':
r_y, r_x = i, ii
if boards[i][ii] == 'G':
g_y, g_x = i, ii
# BFS (처음 로봇 위치 y, x, 이동횟수)
queue = deque([(r_y, r_x, 0)])
visited = set()
visited.add((r_y, r_x))
while queue:
ry, rx, depth = queue.popleft()
# 도착지점에 도착
if (ry, rx) == (g_y, g_x):
return depth
for dy, dx in move:
nry, nrx = r_move(boards, ry, rx, dy, dx)
if (nry, nrx) not in visited:
visited.add((nry, nrx))
queue.append((nry, nrx, depth + 1))
return -1
# 로봇이 움직이는 로직
def r_move(boards, y, x, dy, dx):
while True:
ny, nx = y + dy, x + dx
# 경계 밖이거나 장애물이면 현재 자리에서 멈춤
if ny < 0 or nx < 0 or ny >= len(boards) or nx >= len(boards[0]) or boards[ny][nx] == 'D':
return y, x
# 한 칸 전진
y, x = ny, nx
핵심 알고리즘은 다음과 같습니다.
# 구슬 시작, 탈출 지점을 정할 변수 입니다.
r_y, r_x, g_y, g_x = 0, 0, 0, 0
# 반복문을 통해 구슬 위치를 먼저 찾습니다.
for i in range(len(boards)):
for ii in range(len(boards[0])):
if boards[i][ii] == 'R':
r_y, r_x = i, ii
if boards[i][ii] == 'G':
g_y, g_x = i, ii
# BFS (처음 로봇 위치 y, x, 이동횟수)
# BFS를 통해서 4방향의 구슬이동 과정 시뮬레이션을 진행할 예정입니다.
queue = deque([(r_y, r_x, 0)])
# set()를 통해서 중복되는 경우는 제거합니다. ex) (1,1)를 재방문하는 문제 제거
visited = set()
visited.add((r_y, r_x))
# queue를 통해 반복문을 수행합니다 만약 도착점이 없는 경우 -1를 반환합니다.
while queue:
ry, rx, depth = queue.popleft()
# 도착지점에 도착
if (ry, rx) == (g_y, g_x):
return depth
# 4방향의 경로를 확인합니다.
for dy, dx in move:
# 로봇이 움직이는 로짓은 밑에 r_move에서 구현했습니다.
nry, nrx = r_move(boards, ry, rx, dy, dx)
# 움직여서 도착한 지점이 만약 방문하지 않았던 지점이라면 다시 queue에 넣습니다.
if (nry, nrx) not in visited:
visited.add((nry, nrx))
queue.append((nry, nrx, depth + 1))
return -1
# 로봇이 움직이는 로직
def r_move(boards, y, x, dy, dx):
while True:
ny, nx = y + dy, x + dx
# 경계 밖이거나 장애물이면 현재 자리에서 멈춤
if ny < 0 or nx < 0 or ny >= len(boards) or nx >= len(boards[0]) or boards[ny][nx] == 'D':
return y, x
# 한 칸 전진
y, x = ny, nx

※ 알아야 할 것
https://www.acmicpc.net/problem/13460
백준에 유사한 문제로 구슬탈출 2 문제가 있습니다!
'Coding Test > 프로그래머스-Python' 카테고리의 다른 글
| Programmers / 상담원 인원 / Python (0) | 2025.11.13 |
|---|---|
| Programmers / 미로 탈출 / Python (0) | 2025.04.03 |
| Programmers / N-Queen / Python (0) | 2025.03.31 |
| Programmers / 숫자 카드 나누기 / Python (0) | 2025.03.27 |
| Programmers / 전력망을 둘로 나누기 / Python (0) | 2025.03.26 |