[프로그래머스]Lv2. 리코쳇 로봇(Python)

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

프로그래머스

 

문제 접근

 

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