링크

게임 맵 최단거리

난이도

  • 프로그래머스 난이도 2
    • 기존과 다른게 bfs를 생각해야했다.

문제요약

  • 시작위치0,0에서 끝위치 m,n가지의 최단경로를 구하시오
    • 도달 못하며 -1

접근

    1. bfs구현
      • bfs로 돌면서 입장가능하면 save역할하는 배열을 복사했음 - 시간초과
    1. bfs구현
      • 복사하는 과정을 없앰

간단 알고리즘

  • memo변수
    • map과 같은크기의 행렬
    • 각 요소는 초기값 -1을 넣어준다.
    • 요소의 값의 의미는 해당 위치까지 가는 최단경로를 저장한다.
  • bfs
    • [x,y,해당경로까지의 비용]으로 큐가 들어간다.
    • 반복
      • 큐가 없을때 - 종료
      • 현재위치의 비용 >= memo의 값이면 다음 진행
      • memo에 현재위치 비용을 넣어준다.
      • 위, 아래, 왼쪽, 오른쪽 이동가능한지 확인하고 큐에 넣어준다.
        • 확인(끝인지, map정보로 벽이 아닌지, memo로 -1이거나 memo >= 현재위치비용 일때)

후기

  • 어렵진 않았는데 자주 copy를 애용하다보니 문제가 되었다.
  • memo에 max값 넣어도되지만 18번인가에서 실패가뜬다.
    • INF를 쓰거나 해야하지만 단순히-1로 넣었다.