[프로그래머스] 리코체 로봇 (파이썬)

난이도 : LV2

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/169199

문제해결

• 전형적인 bfs 탐색 문제에서 상하좌우 조건 부분만 수정한다.
• 상하좌우 탐색시 벽에 부딪히거나, 장애물을 만났을 경우까지 이동시킨다.
• visited 는 매번 움직일때마다가 아닌 위 조건을 충족했을 때에만 기록한다.

소스코드

from collections import deque

dx, dy = [0,0,-1,1], [1,-1,0,0]

def solution(board):
    n = len(board)
    m = len(board[0])
    q = deque()
    cur = (0,0)
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                cur = (i,j)
    visited = [[0] * m for _ in range(n)]
    q.append(cur)
    visited[cur[0]][cur[1]] = 1
    
    while q:
        x,y = q.popleft()
        if board[x][y] == 'G': #목표 지점에 도달했을 경우 값을 리턴하고 종료한다.
            return visited[x][y] - 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            while 0<=nx<n and 0<=ny<m and board[nx][ny] != 'D': #벽에 부딪히거나 장애물을 만날때까지 반복
                nx += dx[i]
                ny += dy[i]
            
            nx -= dx[i] #벽에 부딪히거나 장애물을 만났으므로 다시 뺴줌
            ny -= dy[i]
            
            if not visited[nx][ny]:
                q.append((nx,ny))
                visited[nx][ny] = visited[x][y] + 1
            
    return -1 # 끝까지 수행했다는 것은 목표지점에 도달하지 못했으므로