[알고리즘 문제 풀이][파이썬] 프로그래머스: 리코쳇 로봇

프로그래머스 리코쳇 로봇 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/169199

📑 문제 설명
1. 리코쳇 로봇이라는 "격자 모양의" 보드게임
2. 보드는 빈공간을 의미하는 '.', 시작점을 의미하는 'R', 도착점을 의미하는 'G', 장애물 'D'로 구성됨
3. R에서 시작하여 G로 도착하는 게임이고 이동 최소 거리를 구해야 함
4. 이동 규칙은 아래와 같음
- 상하좌우로 한 칸씩 이동하는 것이 아니라 상하좌우로 'D' 또는 벽을 만날 때까지 이동

입력: 보드게임판
출력: 최소 이동 거리

💡 문제 해결 방법
알고리즘: BFS

1. DFS + 백트래킹으로 했더니 시간초과 남 --> 여기서 DFS를 사용할 경우 다음 이동 칸보다 현재 이동 거리가 작을 때만 이동하여 쓸데없이 같은 길을 여러번 가지 않도록 조건문 달아야 함
2. BFS를 구현하였고 visit 배열을 사용함
   • visit 배열로 이동거리를 측정함(q에 x, y 위치만 삽입함)

예외처리 및 추가 내용
1. 한 칸 씩 이동이 아닌, 'D' 또는 벽을 만날 때까지 이동해야 하기 때문에 [1, 0], [-1, 0], [0, 1], [0, -1] 로 while 문을 사용하여 구현함. 이와 같은 위치 좌표 리스트가 이런 문제에 훨씬 용이하기 때문에 앞으로 위와 같이 쓰는 습관을 들일 것

💻 코드

from collections import deque
def solution(board):
    answer = 0
    r = len(board)
    c = len(board[0])
    for i in range(len(board)):
        temp = board[i]
        for j in range(len(temp)):
            if temp[j] == 'R':
                sx, sy = i, j
            elif temp[j] == 'G':
                dx, dy = i, j
    
    visit = [[10**8 for x in range(c)]for _ in range(r)]
    
    def bfs(q, visit):
        while q:
            x, y = q.popleft()
            if x == dx and y == dy:
                break
                return
            adjlist = [[-1, 0], [1, 0], [0, -1], [0, 1]]         
            for addx, addy in adjlist:
                cx, cy = x, y
                while True:
                    nx, ny = cx + addx, cy + addy
                    if 0<=nx<r and 0<= ny <c:
                        if board[nx][ny]=='D':
                            if visit[cx][cy] == 10**8:
                                q.append((cx, cy))
                                visit[cx][cy] = visit[x][y]+1
                                break
                            break
                        cx, cy = nx, ny
                        continue
                    elif nx < 0 or ny < 0 or nx > r-1 or ny > c-1:
                        if visit[cx][cy] == 10**8:
                            q.append((cx, cy))
                            visit[cx][cy] = visit[x][y]+1
                        break
                    
    visit[sx][sy] = 0
    q = deque([(sx, sy)])
    bfs(q, visit)
    if visit[dx][dy] == 10**8:
        answer = -1
    else:   answer = visit[dx][dy]
    return answer

💟 추가적으로 알게 된 점
1. adjlist를 숫자로만 조합하여 사용하기
2. 조건문을 단축시킬 아이디어 고민해보기

+) 끝까지 포기하지 않아서 뿌듯한데 진이 너무 빠지는...

참고