리코쳇 로봇

프로그래머스

 

BFS를 활용하면 되는 문제.

기본 BFS 문제 로직과 거의 유사하지만 다른 점이 한 가지 있다.

로봇이 한 칸씩 이동하는 게 아니라, 장애물에 부딪히거나 맵의 끝에 도달할 때까지 한 방향으로 계속 이동하고, 멈췄을 때까지 시간을 1로 친다는 것이다.

그 부분을 반복문을 통해 구현해줬다.

 

---

풀이 코드

from collections import deque

def solution(board):
    
    n = len(board) # 행 길이
    m = len(board[0]) # 열 길이
    
    visited = [[0] * m for _ in range(n)] # 방문 여부 저장
    
    start = [] # 출발점
    
    # 출발점, 도착점 입력
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                start = (i, j)

                
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    
    q = deque([start]) # 출발점 큐에 넣기
    visited[start[0]][start[1]] = 1 # 출발거리는 1로 초기화
    

    
    while q:
        x,y = q.popleft()
        
        if board[x][y] == 'G':
            return visited[x][y] - 1 # 출발지점의 거리를 1로 초기화했으므로 총 거리에서 1을 빼줘야 실제 거리가 나온다.
        
        for i in range(4):
            nx = x
            ny = y
            # 게임 판 위 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동
            while True:
                # 계속 더함
                nx += dx[i]
                ny += dy[i]
                # 맨 끝에 도달한 경우
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    break
                # 장애물에 부딪힌 경우
                if board[nx][ny] == 'D':
                    break
            
            # 부딪힌 칸 바로 전칸으로 이동    
            nx -= dx[i]
            ny -= dy[i]
            
            # 방문하지 않은 칸이라면 큐에 추가하고 거리 갱신
            if not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = visited[x][y] + 1
                
    # 큐가 빌 때까지 리턴하지 도착점에 도달하지 못했다면 -1 리턴
    return -1

 

반복문에서 nx를 계속 갱신해주는 부분에서 nx += dx[i]로 해야하는데, nx = x + dx[i]로 해서 무한루프를 도는 문제를 찾느라 시간이 좀 걸렸다.

그 외에는 큰 어려움이 없던 문제.