[프로그래머스/Python] 리코쳇 로봇

📌 문제

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

문제 내 예시는 아래 이미지와 같이 움직이게 되며 규칙은 아래와 같다.

• 시작점 R에서 시작한다.
• 범위 안에서 돌아다닐 수 있다.
• D를 만날때까지 특정 방향으로 계속 움직이다.
• G를 지나갈수 있다. 아래 이미지의 2번 움직임을 봤을때 G에서 서는 것이 아니라 G를 지나쳐 D앞에서 멈추게 된다. (처음에 2번만에 끝날수 있는거 아닌가.. 했슴돠 😭)
• 정확하게 G에 서야한다.
  

만약 이해가 안된다면 아래 동영상을 꼭 보면 좋습니다!!! 동작원리를 쉽게 이해할수 있어요
https://www.youtube.com/watch?v=QqSREKrNSIg

📌 풀이

풀이 1 - (11,20,24,26번 테스트 케이스 실패)

1. 입력으로 주어진 보드를 이차원 리스트 graph에 저장한다.
2. chk는 최소 이동 횟수를 기록하는 이차원 리스트로, 모든 값을 무한대(float('inf'))로 초기화한다.
3. 이중 반복문을 사용하여 출발과 도착 위치를 찾아 start_y, start_x, end_y, end_x 변수에 저장한다.
4. BFS 함수 호출한다.

• bfs 함수는 시작점부터 도착점까지의 최소 이동 횟수를 계산하는 함수이다.
• 네 방향 (상, 하, 좌, 우)으로 이동할 수 있는지 확인하고, 이동할 수 있다면 이동한 후의 위치를 계산한다.
• 만약 이동한 위치의 최소 이동 횟수가 현재 위치의 최소 이동 횟수보다 크다면, 최소 이동 횟수를 업데이트하고 해당 위치를 큐에 추가한다.

5. 결과가 None이라면 도착점에 도달할 수 없는 경우이므로 -1을 반환한다.

from collections import deque

def solution(board):
    n, m = len(board), len(board[0])
    graph = [list(board[i]) for i in range(n)]
    chk = [[float('inf')] * m for _ in range(n)]

    # 시작점, 도착점 찾기
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'R':
                start_y, start_x = i, j
            elif graph[i][j] == 'G':
                end_y, end_x = i, j
    chk[start_y][start_x] = 0

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

    def move_there(dir_y, dir_x, c_y, c_x):
        while True:
            c_y = c_y + dir_y
            c_x = c_x + dir_x

            if 0 > c_y or c_y >= n or 0 > c_x or c_x >= m or (graph[c_y][c_x] == 'D'):
                return [c_y - dir_y, c_x - dir_x]

    def bfs(s_y, s_x, e_y, e_x):
        q = deque()
        q.append((s_y, s_x))

        while q:
            y, x = q.popleft()
            if y == e_y and x == e_x:
                return chk[e_y][e_x]
            for k in range(4):
                ny = y + dy[k]
                nx = x + dx[k]
                if 0 <= ny < n and 0 <= nx < m:
                    if graph[ny][nx] == '.':
                        ny, nx = move_there(dy[k], dx[k], y, x)
                        if chk[ny][nx] > chk[y][x] + 1:
                            chk[ny][nx] = chk[y][x] + 1
                            q.append((ny, nx))
    
    result = bfs(start_y, start_x, end_y, end_x)
    
    if result is None:
        return -1
    else:
        return result

풀이 2 - (성공)

'.' 뿐만 아니라 'R', 'G'도 지나칠 수 있다. 이전 코드에선 if graph[ny][nx] == '.'로 되어있어 테케 통과가 되지 않음을 알 수 있다.
'D'가 아닌곳이라면 지나갈 수 있도록 수정했다!

from collections import deque

def solution(board):
    n, m = len(board), len(board[0])
    graph = [list(board[i]) for i in range(n)]
    chk = [[float('inf')] * m for _ in range(n)]

    # 시작점, 도착점 찾기
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 'R':
                start_y, start_x = i, j
            elif graph[i][j] == 'G':
                end_y, end_x = i, j
    chk[start_y][start_x] = 0

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

    def move_there(dir_y, dir_x, c_y, c_x):
        while True:
            c_y = c_y + dir_y
            c_x = c_x + dir_x

            if 0 > c_y or c_y >= n or 0 > c_x or c_x >= m or (graph[c_y][c_x] == 'D'):
                return [c_y - dir_y, c_x - dir_x]

    def bfs(s_y, s_x, e_y, e_x):
        q = deque()
        q.append((s_y, s_x))

        while q:
            y, x = q.popleft()
            if y == e_y and x == e_x:
                return chk[e_y][e_x]
            for k in range(4):
                ny = y + dy[k]
                nx = x + dx[k]
                if 0 <= ny < n and 0 <= nx < m:
                    if graph[ny][nx] != 'D': #수정한곳 
                        ny, nx = move_there(dy[k], dx[k], y, x)
                        if chk[ny][nx] > chk[y][x] + 1:
                            chk[ny][nx] = chk[y][x] + 1
                            q.append((ny, nx))
    
    result = bfs(start_y, start_x, end_y, end_x)
    
    if result is None:
        return -1
    else:
        return result