프로그래머스_level 2_리코쳇 로봇(python)

※ 접근법

1. 그래프가 주어지고 최소의 경우의 수를 구해야 하니 탐색을 떠올렸다.

2. 보드의 크기가 최대 100, 100 총 만 칸이니 dfs로 탐색할 시 RecursionError가 발생할 것 같아 bfs로 풀기로 했다.

 

※ 풀이

1.  미로에서 상하좌우로 이동하는데 빙판길이라고 생각했다.

2. 장애물("D"), 벽("그래프 범위를 벗어나기 전 가장자리")을 만나기전 까지 계속 미끄러진다.

3. 목표지점을 만났다면 바로 리턴해서 함수를 종료해준다. (바로 리턴해줄 수 있는 이유는 밑에 나온다.)

4. 벽이나 장애물을 만났는데 count > 0이면서 전에 방문했을 때보다 더 작은 횟수로 방문했을 시 큐에 추가해주고 visited값을 갱신해준다. (이렇게 최소 횟수의 방법만 큐에 들어오니 목표지점 도착했을 때도 최소 방법으로 도착했을 것이고 그래서 바로 리턴해주는 것이다.)

 

from collections import deque

def bfs(r,c,row,col,data):
    visited = [[float("inf")] * col for i in range(row)]
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    q = deque()
    q.append((r,c))
    visited[r][c] = 0
    while q:
        x,y = q.popleft()
        fx,fy = x,y
        for i in range(4):
            count = 0
            x,y = fx,fy # 반복을 할 때마다 x랑 y가 변한채로 진행이 되니 첫 시작을 다시 넣어줘야 한다.
            while True:
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 > nx or nx == row or 0 > ny or ny == col or data[nx][ny] == 'D':
                    if data[x][y] == 'G':
                        return visited[fx][fy] + 1
                    if count > 0 and visited[fx][fy] + 1 < visited[x][y] : 
                        q.append((x,y))
                        visited[x][y] = visited[fx][fy] + 1
                    break
                x,y = nx,ny
                count += 1
    return -1
    
def solution(board):
    row = len(board)
    col = len(board[1])
    for i in range(row):
        for j in range(col):
            if board[i][j] == "R":
                return bfs(i,j,row,col,board)

 

※ 회고

큐에서 x,y를 팝하고 fx,fy에다가 기억만 시켜놓고 다시  매 반복 때마다 x,y에다가 넣어주지 않았다. 반복 할 때마다 x,y 값은 변할텐데. 이렇게 변수가 계속 변할 때 변수의 변화에 대해 주의하자