[프로그래머스] 169199. 리코쳇 로봇 | BFS | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

상하좌우 중 한 방향을 선택해 장애물이나 벽에 부딪힐때까지 이동하여 목표 지점에 도달하는 보드게임이 있다.

목표지점에 도달하기위한 최소 이동 횟수를 구하라

---

문제 조건

• .은 빈공간, D는 장애물, R은 시작지점, G는 목표지점이다
• 보드판 가로의 길이와 세로의 길이는 다를 수 있다

---

시행착오

처음에 보드판 가로길이와 세로길이가 동일한줄알고 풀었다. 출력예시만 봐도 알 수 있는건데... 

---

접근방식

• bfs로 풀었다. 이동횟수를 저장하기 위해 2차원 배열 matrix를 정의했다

 

---

소스코드

from collections import deque

def solution(board):
    answer = -1
    start_x, start_y = 0, 0
    N, M = len(board), len(board[0])
    matrix = [[-1]*M for _ in range(N)]

    for i in range(N):
        for j in range(M):
            if board[i][j] == 'G':
                goal_x = i
                goal_y = j
            if board[i][j] == 'R':
                start_x = i
                start_y = j

    q = deque([[start_x, start_y]])
    matrix[start_x][start_y] = 0

    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]

    while q:
        x, y = q.popleft()

        if board[x][y] == 'G':
            answer = matrix[x][y]
            break

        for i in range(4):
            nx, ny = x, y
            while 0 <= (nx + dx[i]) < N and 0 <= (ny + dy[i]) < M:
                if board[nx + dx[i]][ny + dy[i]] == 'D':
                    break
                nx += dx[i]
                ny += dy[i]

            if matrix[nx][ny] == -1:
                q.append([nx, ny])
                matrix[nx][ny] = matrix[x][y] + 1

    return answer