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

리코쳇 로봇

프로그래머스

 

 

 

• 내 풀이 - BFS
  • 벽이나 장애물에 부딪칠때까지 while문으로 이동
  • 부딪치면 그 전 위치 반납하는게 일반 dfs와 차이
  • 가장 먼저 return 된게 가장 최단거리

from collections import deque

def solution(board):
    board = [list(b.rstrip()) for b in board]
    n = len(board)
    m = len(board[0])

    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    visited = [[False] * m for _ in range(n)]

    queue = deque()
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                queue.append((i, j, 0))
                visited[i][j] = True
                break

    while queue:
        i, j, cnt = queue.popleft()

        if board[i][j] == 'G':
            return cnt

        for k in range(4):
            x, y = i, j

            while True:
                nx = x + dx[k]
                ny = y + dy[k]
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    break
                if board[nx][ny] == 'D':
                    break
                x, y = nx, ny

            if visited[x][y]:
                continue
                
            visited[x][y] = True
            queue.append((x, y, cnt + 1))

    return -1

 

 

• DFS
  • 최단거리 문제이기 때문에 재귀는 비효율적이긴 함
  • 가지치기 필수
    • → 이미 더 짧은 거리로 방문한 지점이라면 다시 안 가야 함

def solution(board):
    board = [list(row.rstrip()) for row in board]
    n = len(board)
    m = len(board[0])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    answer = float('inf')

    dist = [[float('inf')] * m for _ in range(n)]

    def dfs(i, j, cnt):
        nonlocal answer

        if dist[i][j] <= cnt:
            return
        dist[i][j] = cnt

        if board[i][j] == 'G':
            answer = min(answer, cnt)
            return

        for k in range(4):
            x, y = i, j
            while True:
                nx = x + dx[k]
                ny = y + dy[k]
                if nx < 0 or ny < 0 or nx >= n or ny >= m:
                    break
                if board[nx][ny] == 'D':
                    break
                    
                x, y = nx, ny
                
            if dist[x][y] > cnt + 1:
                dfs(x, y, cnt + 1)

    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                dfs(i, j, 0)
                break

    return answer if answer != float('inf') else -1