Programmers / 리코쳇 로봇 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 리코쳇 로봇 (2단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/169199

프로그래머스

 

문제 설명

---

나의 풀이

from collections import deque


def solution(board):
    move = [(0, 1), (1, 0), (-1, 0), (0, -1)]

    boards = []

    for i in board:
        boards.append(list(i))

    r_y, r_x, g_y, g_x = 0, 0, 0, 0

    for i in range(len(boards)):
        for ii in range(len(boards[0])):
            if boards[i][ii] == 'R':
                r_y, r_x = i, ii
            if boards[i][ii] == 'G':
                g_y, g_x = i, ii

    # BFS (처음 로봇 위치 y, x, 이동횟수)
    queue = deque([(r_y, r_x, 0)])
    visited = set()
    visited.add((r_y, r_x))

    while queue:
        ry, rx, depth = queue.popleft()
        
        # 도착지점에 도착
        if (ry, rx) == (g_y, g_x):
            return depth
        
        for dy, dx in move:
            nry, nrx = r_move(boards, ry, rx, dy, dx)
            if (nry, nrx) not in visited:
                visited.add((nry, nrx))
                queue.append((nry, nrx, depth + 1))

    return -1


# 로봇이 움직이는 로직
def r_move(boards, y, x, dy, dx):
    while True:
        ny, nx = y + dy, x + dx

        # 경계 밖이거나 장애물이면 현재 자리에서 멈춤
        if ny < 0 or nx < 0 or ny >= len(boards) or nx >= len(boards[0]) or boards[ny][nx] == 'D':
            return y, x

        # 한 칸 전진
        y, x = ny, nx

핵심 알고리즘은 다음과 같습니다.

    # 구슬 시작, 탈출 지점을 정할 변수 입니다.
    r_y, r_x, g_y, g_x = 0, 0, 0, 0
    
    # 반복문을 통해 구슬 위치를 먼저 찾습니다.
    for i in range(len(boards)):
        for ii in range(len(boards[0])):
            if boards[i][ii] == 'R':
                r_y, r_x = i, ii
            if boards[i][ii] == 'G':
                g_y, g_x = i, ii

    # BFS (처음 로봇 위치 y, x, 이동횟수)
    # BFS를 통해서 4방향의 구슬이동 과정 시뮬레이션을 진행할 예정입니다.
    queue = deque([(r_y, r_x, 0)])
    # set()를 통해서 중복되는 경우는 제거합니다. ex) (1,1)를 재방문하는 문제 제거
    visited = set()
    visited.add((r_y, r_x))
    
    # queue를 통해 반복문을 수행합니다 만약 도착점이 없는 경우 -1를 반환합니다.
    while queue:
        ry, rx, depth = queue.popleft()
        
        # 도착지점에 도착
        if (ry, rx) == (g_y, g_x):
            return depth
        
        # 4방향의 경로를 확인합니다.
        for dy, dx in move:
        	# 로봇이 움직이는 로짓은 밑에 r_move에서 구현했습니다.
            nry, nrx = r_move(boards, ry, rx, dy, dx)
            # 움직여서 도착한 지점이 만약 방문하지 않았던 지점이라면 다시 queue에 넣습니다.
            if (nry, nrx) not in visited:
                visited.add((nry, nrx))
                queue.append((nry, nrx, depth + 1))

    return -1


# 로봇이 움직이는 로직
def r_move(boards, y, x, dy, dx):
    while True:
        ny, nx = y + dy, x + dx

        # 경계 밖이거나 장애물이면 현재 자리에서 멈춤
        if ny < 0 or nx < 0 or ny >= len(boards) or nx >= len(boards[0]) or boards[ny][nx] == 'D':
            return y, x

        # 한 칸 전진
        y, x = ny, nx

---

※ 알아야 할 것

https://www.acmicpc.net/problem/13460

백준에 유사한 문제로 구슬탈출 2 문제가 있습니다!