프로그래머스 - 리코쳇 로봇 [연습문제]

문제 설명:

리코쳇 로봇이라는 보드게임이 있습니다.

이 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 출발한 뒤 목표 위치에 정확하게 멈추기 위해 최소 몇 번의 이동이 필요한지 말하는 게임입니다.

이 게임에서 말의 이동은 현재 위치에서 상, 하, 좌, 우 중 한 방향으로 게임판 위의 장애물이나 게임판 가장자리까지 부딪힐 때까지 미끄러져 움직이는 것을 한 번의 이동으로 정의합니다.

다음은 보드게임판을 나타낸 예시입니다. ("."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.)

... D.. R
. D.G...
.... D.D
D.... D.
.. D....
이때 최소 움직임은 7번이며 "R" 위치에서 아래, 왼쪽, 위, 왼쪽, 아래, 오른쪽, 위 순서로 움직이면 "G" 위치에 멈춰 설 수 있습니다.

게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성해 주세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.

---

문제 예시:

board	result
["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]	7
[".D.R", "....", ".G..", "...D"]	-1

---

문제 해결:

from collections import deque

def solution(board):
    dx = len(board)
    dy = len(board[0])
    board = ''.join(board)
    d = [1, -1, dy, -dy]
    
    INF = 1e+6
    
    distance = [INF] * len(board)
    
    cur = board.index('R')
    
    def move(idx, m):
        while True:
            nxt = idx + m

            if nxt < 0 or nxt >= len(board):
                return idx

            if m == 1 or m == -1:
                if (nxt // dy) != (idx // dy):
                    return idx

            if board[nxt] == 'D':
                return idx

            idx = nxt
    
    q = deque()
    q.append((cur, 0))
    distance[cur] = 0
    
    while q:
        node,cnt = q.popleft()
        
        if board[node] == 'G':
            return cnt
        
        for i in range(4):
            nodeMoved = move(node, d[i])
            
            if distance[nodeMoved] > cnt+1:
                distance[nodeMoved] = cnt+1
                q.append((nodeMoved, cnt+1))
    
    return -1

코드가 상당히 길다.

먼저 사용한 것은 dijkstra이고 나는 board 2D array를 flatten 시켜서 움직였다.

move라는 함수를 통해 다음 node의 위치를 return하게 하였다.

 

move 시에는 몇가지 봐야 할 것이 있는데 바로 dx, dy 만큼 이동했을 때 valid 했는지 아닌지 체크하는 것이다.

먼저 nxt가 0보다 작거나 len(board)보다 크면 index out of range이므로 idx를 준다 (다른 말로는 경계라는 뜻이다)

 

이후, m이 1이거나 -1이면 넘겼을 때 아랫줄 혹은 윗줄로 넘어가는지 봐야 하는데 이를 dy(첫 번째 array의 length)로 나눴을 때 몫이 바뀌면 윗줄 혹은 아랫줄로 넘어갔다는 뜻이므로 걸러야 한다.

 

마지막으로 nxt가 D면 그 앞에서 멈춰야 하므로 idx를 return한다

 

이 외의 경우는 nxt로 이동한다.

 

그다음은 dijkstra이다.

기본적으로 bfs에 distance의 최솟값 비교라고 생각하면 편하다.

이때 for문은 4로 준 이유는 방향이 4개밖에 없기 때문이다.

---

다른 해설을 보자

def solution(board):
    que = []
    for x, row in enumerate(board):
        for y, each in enumerate(row):
            if board[x][y] == 'R':
                que.append((x, y, 0))
    visited = set()
    while que:
        x, y, length = que.pop(0)
        if (x, y) in visited:
            continue
        if board[x][y] == 'G':
            return length
        visited.add((x, y))
        for diff_x, diff_y in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            now_x, now_y = x, y
            while True:
                next_x, next_y = now_x + diff_x, now_y + diff_y
                if 0 <= next_x < len(board) and 0 <= next_y < len(board[0]) and board[next_x][next_y] != 'D':
                    now_x, now_y = next_x, next_y
                    continue
                que.append((now_x, now_y, length + 1))
                break
    return -1

만약 2D로 보겠다면 x, y를 직접 줘서 2D에서 볼 수 있게 해야 하며 2D에 맞는 제한 조건을 주어야 한다.

그 외의 생각은 똑같다.

 

여기서는 visited를 기준으로 자르는데 이게 가능한 경우가 한 가지가 있다.

"Edge의 가중치가 1일 때"

이때는 visited로 잘라도 최솟값이 보장된다.