[Programmers] 리코쳇 로봇 (Python)

📖문제

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

프로그래머스

✨핵심 내용 

상, 하, 좌, 우 4방향 중 하나를 선택해서
게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 친다. 

🤔해결 아이디어 

유형: BFS

초기 데이터

 

R에서 시작하여 미끄러져 이동하며 G에 도착해야 한다. 

-> 일반적인 최단거리 BFS 문제에서 이동 거리(방식)를 조정해 주면 된다! 

매 턴 로봇의 도착 위치 (3턴 까지 표시)

위의 그림과 같이 로봇의 도착 위치를 표시할 수 있다. 

로봇의 현재 위치에서 상하좌우 중 이동 가능한 위치로 이동 시키며 경로를 확인하면 된다. 

도착 위치를 visited 배열에 이동 횟수로 표시하며 이동한다. 

 

🟡 주의 할 점

    # 이동 함수 - 한 번에 미끌어지듯 이동
    def move(x, y, dx, dy):
        nx, ny = x + dx, y + dy
        while in_range(nx, ny) and board[nx][ny] != 'D':
            nx += dx
            ny += dy
            
        return nx - dx, ny - dy # D 위치에서 while 문이 정지되므로 한 칸씩 뒤로 가야 한다.

기존 상하좌우 한 칸씩 이동하는 bfs함수에서는 nx, ny의 위치를 nx, ny = x + dx, y + dy로 잡아주었다. 

 

그러나 리코렛 로봇은 장애물에 닿을 때까지 미끄러지듯 이동해야 하므로 

장애물에 닿을 때 까지 dx, dy 방향으로 이동하는 함수를 작성했다. 

(dx, dy의 방향을 따라 장애물(범위 벗어남, D)을 만나기 전까지 이동하는 코드)

---

✅정답 코드 (Python)

from collections import deque
def solution(board):
    n = len(board)
    m = len(board[0])
    
    dxs, dys = [0, 0, 1, -1], [-1, 1, 0, 0]
    
    # 로봇 초기 위치 등록
    for i in range(n):    
        for j in range(m):
            if board[i][j] == 'R':
                rx, ry = i, j
    
    # bfs 사전 준비
    q = deque()
    q.append((rx, ry))
    visited = [[0 for _ in range(m)] for _ in range(n)]
    visited[rx][ry] = 1
    
    # 범위 체크 함수
    def in_range(x, y):
        if x < 0 or x >= n or y < 0 or y >= m:
            return False
        return True
    
    # 이동 함수 - 한 번에 미끌어지듯 이동
    def move(x, y, dx, dy):
        nx, ny = x + dx, y + dy
        while in_range(nx, ny) and board[nx][ny] != 'D':
            nx += dx
            ny += dy
            
        return nx - dx, ny - dy
    
    def bfs():
        while q:
            x, y = q.popleft()
            for dx, dy in zip(dxs, dys):
                nx, ny = move(x, y, dx, dy) # nx, ny = x + dx, y + dy를 변경
                if in_range(nx, ny) and not visited[nx][ny] and board[nx][ny] != 'D':
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
                    
                    # 종료 조건
                    if board[nx][ny] == 'G':
                        return visited[x][y]
        
        # G 만나지 못하면 -1 리턴
        return -1
    
    ans = bfs()
    
    return ans

🔶 유사 문제

백준_13460 구슬 탈출 2

13460번: 구슬 탈출 2 (acmicpc.net)

 

백준_7562 나이트의 이동

7562번: 나이트의 이동 (acmicpc.net)