[프로그래머스] 리코쳇 로봇 (Lv 2)

솔직히 2단계 치고는 조금 어렵지 않나 싶다.

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

프로그래머스

BFS 문제이다. 이동 불가능할때까지 넣으면 된다.
핵심은 도달하는 순간 끝내고 답 내주면 된다.
그렇기에 도달 기록을 가진 visit에 아예 count를 저장해두면 편하다.
미끄러지는 것을 구현을 이렇게 복잡하게 할 이유는 없긴 하지만 직관적인 방향이라 이 방법대로 갔다.

정통적인 bfs 방법으로도 깔끔하게 될 거 같은데, 행간의 이해는 이게 더 쉽지 않나 싶다.

from collections import deque
def bfs(visit, board):
    m, n = len(board), len(board[0])
    # step 1. 시작점과 도착점을 알아야 함, 좌표를 찾는다.
    # x : 위아래, y : 좌우 기준으로 잡자.
    for i in range(len(board)):
        if 'R' in board[i]:
            start_x = i
            start_y = board[i].find('R')
        if 'G' in board[i]:
            end_x = i
            end_y = board[i].find('G')
    # step 2. BFS 단계 세팅
    # 아이디어는 visit에 최소 횟수를 넣어서 갈거임
    # 따라서 이번에는 -1이 미도달, 0 이상이 도달경험 보유.
    queue = deque()
    queue.append((start_x, start_y))
    visit[start_x][start_y] = 0
    
    while queue:
        x, y = queue.popleft()
        # 현재 까지의 이동 횟수를 받아온다.
        cur_count = visit[x][y]
        # 네가지 방향을 시도해야함
        # 왼쪽 : y > 0일때 유효한 시도임
        if y > 0:
            new_y = y
            while new_y > 0:
                if board[x][new_y-1] != 'D':
                    new_y -= 1
                else:
                    # 돌을 만난거라 좌표를 바꾸지 말고 break
                    break
            # 이동에 성공했다면 좌표가 달라질 것이다.
            # 새로운 좌표일때만 횟수를 넣으면 최솟값임이 보장되어 있다.
            if new_y != y and visit[x][new_y] == -1:
                visit[x][new_y] = cur_count + 1
                queue.append((x, new_y))
                # 도착해버렸으면 즉시 함수 탈출 시켜주자
                if x == end_x and new_y == end_y:
                    return visit[x][new_y]
        # 오른쪽 : y < n-1일때 유효한 시도임
        if y < n-1:
            new_y = y
            while new_y < n-1:
                if board[x][new_y+1] != 'D':
                    new_y += 1
                else:
                    # 돌을 만난거라 좌표를 바꾸지 말고 break
                    break
            # 이동에 성공했다면 좌표가 달라질 것이다.
            # 새로운 좌표일때만 횟수를 넣으면 최솟값임이 보장되어 있다.
            if new_y != y and visit[x][new_y] == -1:
                visit[x][new_y] = cur_count + 1
                queue.append((x, new_y))
                # 도착해버렸으면 즉시 함수 탈출 시켜주자
                if x == end_x and new_y == end_y:
                    return visit[x][new_y]
        # 위쪽 : x > 0일때 유효한 시도임
        if x > 0:
            new_x = x
            while new_x > 0:
                if board[new_x-1][y] != 'D':
                    new_x -= 1
                else:
                    # 돌을 만난거라 좌표를 바꾸지 말고 break
                    break
            # 이동에 성공했다면 좌표가 달라질 것이다.
            # 새로운 좌표일때만 횟수를 넣으면 최솟값임이 보장되어 있다.
            if new_x != x and visit[new_x][y] == -1:
                visit[new_x][y] = cur_count + 1
                queue.append((new_x, y))
                # 도착해버렸으면 즉시 함수 탈출 시켜주자
                if new_x == end_x and y == end_y:
                    return visit[new_x][y]
        # 아래쪽 : x < m-1일때 유효한 시도임
        if x < m-1:
            new_x = x
            while new_x < m-1:
                if board[new_x+1][y] != 'D':
                    new_x += 1
                else:
                    # 돌을 만난거라 좌표를 바꾸지 말고 break
                    break
            # 이동에 성공했다면 좌표가 달라질 것이다.
            # 새로운 좌표일때만 횟수를 넣으면 최솟값임이 보장되어 있다.
            if new_x != x and visit[new_x][y] == -1:
                visit[new_x][y] = cur_count + 1
                queue.append((new_x, y))
                # 도착해버렸으면 즉시 함수 탈출 시켜주자
                if new_x == end_x and y == end_y:
                    return visit[new_x][y]
    return -1

def solution(board):
    m, n = len(board), len(board[0])
    visit = [[-1] * n for _ in range(m)]
    answer = bfs(visit, board)
    return answer