[프로그래머스] 리코쳇 로봇

문제 요약

로봇은 상, 하, 좌, 우 중 한 방향을 선택하면 장애물 또는 보드 경계에 닿을 때까지 미끄러진다.

로봇이 시작 위치 R에서 목표 위치 G에 정확히 멈추기 위한 최소 이동 횟수를 구한다. 목표에 도달할 수 없으면 -1을 반환한다.

핵심 아이디어

한 번의 방향 선택이 한 번의 이동이고, 모든 이동의 비용이 같다. 따라서 각 정지 위치를 정점으로 보고 BFS를 수행하면 목표 위치까지의 최소 이동 횟수를 구할 수 있다.

현재 위치에서 한 방향으로 이동할 때는 한 칸씩 전진한다.

• 다음 칸이 보드 밖이면 현재 위치에서 멈춘다.
• 다음 칸이 D이면 현재 위치에서 멈춘다.
• 그렇지 않으면 계속 전진한다.

멈춘 위치가 다음 BFS 상태다.

풀이 과정

1. 보드에서 시작 위치 R와 목표 위치 G를 찾는다.
2. 시작 위치를 BFS 큐에 넣고 방문 처리한다.
3. 현재 위치에서 네 방향으로 미끄러진 뒤의 위치를 구한다.
4. 아직 방문하지 않은 정지 위치라면 큐에 넣는다.
5. 목표 위치에 처음 도달했을 때의 이동 횟수를 반환한다.
6. 큐가 비어도 목표에 도달하지 못하면 -1을 반환한다.

Python 코드

from collections import deque


def solution(board):
    row_count = len(board)
    col_count = len(board[0])
    start = None
    goal = None

    for row in range(row_count):
        for col in range(col_count):
            if board[row][col] == "R":
                start = (row, col)
            elif board[row][col] == "G":
                goal = (row, col)

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    def slide(row, col, dr, dc):
        while True:
            next_row = row + dr
            next_col = col + dc

            if (
                next_row < 0
                or next_row >= row_count
                or next_col < 0
                or next_col >= col_count
                or board[next_row][next_col] == "D"
            ):
                return row, col

            row, col = next_row, next_col

    visited = [[False] * col_count for _ in range(row_count)]
    start_row, start_col = start
    visited[start_row][start_col] = True
    queue = deque([(start_row, start_col, 0)])

    while queue:
        row, col, move_count = queue.popleft()

        if (row, col) == goal:
            return move_count

        for dr, dc in directions:
            next_row, next_col = slide(row, col, dr, dc)

            # 이미 경계 또는 장애물에 붙어 있어 움직이지 못한 경우
            if (next_row, next_col) == (row, col):
                continue

            if not visited[next_row][next_col]:
                visited[next_row][next_col] = True
                queue.append((next_row, next_col, move_count + 1))

    return -1

예시

첫 번째 예시에서 로봇은 다음 순서로 이동해 목표 위치에 도착할 수 있다.

아래 -> 왼쪽 -> 위 -> 왼쪽 -> 아래 -> 오른쪽 -> 위

총 7번 이동이다.

BFS는 1번 이동으로 도달 가능한 모든 정지 위치를 먼저 확인하고, 그다음 2번 이동으로 도달 가능한 위치를 확인한다. 따라서 목표 위치를 처음 꺼냈을 때의 횟수인 7이 최소 이동 횟수다.

시간 복잡도

R을 행 수, C를 열 수라고 하자.

정지 위치 하나에서 네 방향으로 최대 max(R, C)칸을 확인한다.

• 시간 복잡도: O(R * C * max(R, C))
• 공간 복잡도: O(R * C)

보드의 최대 크기는 100 x 100이므로 충분히 빠르게 동작한다.

정리

로봇이 지나가는 중간 칸이 아니라, 장애물 또는 경계 앞에서 멈춘 위치가 BFS의 상태다. 네 방향으로 미끄러진 결과만 다음 상태로 넣으면 최소 이동 횟수를 구할 수 있다.