[프로그래머스] 리코쳇 로봇 파이썬 정답 풀이

 

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

프로그래머스

---

 

1. 풀이

• 최소 거리를 찾는 bfs의 변형

우선 노드과 노드 간의 최소 거리를 찾는 알고리즘인 bfs를 사용해야 한다.

그러나 일반 bfs는 현재 좌표 (x, y)에서 상하좌우 한 칸씩만 이동하지만, 이 문제에선 장애물이나 게임판 가장자리를 만날 때까지 쭉 이어서 값을 더해줘야 한다. 예를 들어 (x, y)에서 아래로 이동할 때는 (x - 1, y)에서 멈추는지 확인하고 아니라면 (x - 2, y)에서 다시 확인하고 (x - 3, y), (x - 4, y), (x - 5, y) ... 이렇게 계속 한 칸씩 이동하면서 멈춰야 하는지 확인해보는 것이다.

 

 

• 이동 회수를 기록하는 2차원 배열

위 방식대로 쭉 이동하다가 장애물이나 가장자리를 만나 (u, z)에서 멈췄다면 (u, z)의 이동 회수는 시작 지점인 (x, y)의 이동 회수에 1을 더한 결과이다. 즉, move[u][z] = move[x][y] + 1

그러나 문제는 한 좌표에서 네 방향으로 이동할 수 있기 때문에 현재 멈춰 있는 (u, z)가 이전에 멈춰선 적이 있던 곳일 수도 있다. 따라서 현재의 move[u][z]보다 move[x][y] + 1이 더 클 수도 있고 그 반대일 수도 있다는 것에 유의해야 한다. 따라서 최종적으로 move[u][z] = min(move[x][y] + 1, move[u][z])를 통해 (u, z)에 도달하는 최소 이동 회수를 구하게 된다.

 

 

• 한 번 방문해서 상하좌우로 이동한 적 있는 곳은 재방문하지 말자

문제에 나온 예제를 들어 설명하겠다. 처음 시작인 (0, 6)에서 아래로 내려가면 (1, 6)에서 멈춘다. 그럼 이제 (1, 6)에서 다시 상하좌우로 이동해야 하는데, 이때 위로 올라가면 처음에 (1, 6)에 도달하기 전에 출발했던 (0, 6)으로 되돌아간다. 어쨌거나 (0, 6)에 왔으니 다시 상하좌우로 이동하면 다시 (1, 6)을 방문하게 되고, 그럼 다시 또 (1, 6)에서 (0, 6)으로 돌아가고... 이 행위를 무한 반복하게 된다.

그러므로 이미 방문해서 상하좌우로 이동한 좌표는 방문 표시 visited[x][y] = True를 하여 다시 방문하지 못하도록 해야 한다.

 

 

 

 

2. 정답 코드

from collections import deque


def solution(board):
    n, m = len(board), len(board[0])
    a, b = find_R(n, m, board)
    
    answer = bfs(a, b, n, m, board)
    
    return answer


def find_R(n, m, board):
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                return i, j

    
def bfs(a, b, n, m, board):
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    move = [[99999] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    
    queue = deque([(a, b)])
    move[a][b] = 0
    
    while queue:
        x, y = queue.popleft()
        
        for d in directions:
            u, z = x, y
            
            while True:
                du, dz = u + d[0], z + d[1]
            
                if not is_validated(du, dz, n, m):
                    break
            
                if board[du][dz] == 'D':
                    break
                
                u, z = du, dz
            
            move[u][z] = min(move[x][y] + 1, move[u][z])
            
            if board[u][z] == 'G':
                return move[u][z]
            
            if not visited[u][z]:
                queue.append((u, z))
        
        visited[x][y] = True
    
    return -1

            
def is_validated(a, b, n, m):
    return 0 <= a < n and 0 <= b < m