[Python 문제 풀이] 프로그래머스 '리코쳇 로봇'

Programmers Lv.2 '리코쳇 로봇' 파이썬 코드 및 풀이

Ice Path Puzzle

리코쳇 로봇이라는 보드게임에 나오는 유명한 알고리즘이다. 흔히 빙판길에서 목표지점까지 이동하는 형태로 옛날 고전게임 등에 퍼즐로 많이 등장한다. 

조건파악

board의 크기 자체는 크지 않다. 그리고 ice slide 문제는 반복횟수가 그렇게 많지 않다.

접근

Ice Slide 문제는 BFS를 이용해 푼다!
 
탐색지점은 항상 상하좌우 방향의 네 곳이 된다.

각 방향의 탐색은 해당 방향으로 +1씩 계산하며 벽 또는 블럭이 나오기 직전 지점을 기록한다.

이동횟수가 적은 지점을 우선으로 하여 탐색을 반복하면 자연스럽게 BFS를 구형하게 된다.
 
BFS와 별개로 각 방향을 탐색하기 위해 1차원탐색을 해야하기 때문에 구현이 조금 까다롭다.

의사코드

BFS알고리즘을 이용해 전체탐색한다.

구현

from collections import deque
def solution(board):
    answer = 0
    rows,cols = len(board), len(board[0])
    start = []
    now = []
    goal = []
    path = deque()
    distance = 0
    visited = [[False for _ in range(cols)] for _ in range(rows)]
    for i,row in enumerate(board) :
        if 'R' in row :
            j = row.index('R')
            start = [i,j,0]
            now = start
            visited[i][j] = True
        if 'G' in row :
            j = row.index('G')
            goal = [i,j]
    # find next coordinates
    while True :
        s0, s1,distance = now
        distance += 1

        # right
        for i in range(s0,rows) :
            if board[i][s1] == 'D' :
                path.append([i- 1, s1, distance])
                break
            elif i == rows - 1 :
                path.append([rows - 1, s1, distance])
                break
        # left
        for i in range(s0,-1,-1) :
            if board[i][s1] == 'D' :
                path.append([i + 1, s1, distance])
                break
            elif i == 0 :
                path.append([0, s1, distance])
                break
        # up
        for i in range(s1,cols) :
            if board[s0][i] == 'D' :
                path.append([s0, i - 1, distance])
                break
            elif i == cols - 1 :
                path.append([s0, cols - 1, distance])
                break
        # down
        for i in range(s1,-1,-1) :
            if board[s0][i] == 'D' :
                path.append([s0, i + 1, distance])
                break
            elif i == 0 :
                path.append([s0, 0, distance])
                break
        # avoid loop
        while True :
            if len(path) != 0 :
                now = path.popleft()
            else :
                return -1
            if not visited[now[0]][now[1]] :
                visited[now[0]][now[1]] = True
                break

        # end condition
        if goal[0] == now[0] and goal[1] == now[1] :
            distance = now[2]
            answer = distance
            break
    return answer

가독성은 개나 줘버린 코드..