프로그래머스 - 게임 맵 최단거리

문제 설명

위 그림과 같은 배열에서 (0, 0) -> (5, 5)로 가는 경우 중 가장 짧은 거리를 도출하고, 만약 도착할 수 없는 경우 -1을 출력하는 문제다.

접근 방식

• dfs로 접근하다 bfs로 변경 (dfs로 실패)
  
  
• 움직이는 방향을 위한 dx, dy 설정
  -> [-1, 1, 0, 0] , [0, 0, -1, 1]
  
  
• 이동 가능한 위치를 저장하기 위한 배열 선언
  
  
• 배열에 이동 가능한 위치가 있는 경우만 돌아가는 while문을 선언, 배열의 첫 번째 요소 추출
  
  
• 이동 가능한 방향 (dx, dy)에 대해 가능한 위치만 배열에 추가
  -> 경계값 고려 필수 (0, 배열 범위 넘어가는지 등), 배열의 값을 1씩 증가 시킴
  
  
• 도달해야 하는 곳의 값이 초기 값인 경우 도달할 수 없음을 의미
  -> if문 이용해 최종 결과 도출

작성한 코드

def solution(maps):
    n, m = len(maps)-1, len(maps[0])-1
    answer = 0
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    way = [[0,0]]
    
    while way:
        x,y = way.pop(0)
        
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if 0 <= nx <= n and 0 <= ny <= m and maps[nx][ny] == 1:
                maps[nx][ny] = maps[x][y] + 1      # 경로 비용 설정
                way.append((nx, ny))
    
    dest = maps[n][m]

    if dest == 1:
        answer = -1
    else:
        answer = dest
        
    return answer