TIL 06-29 게임 맵 최단거리

문제 정보

• 문제 이름: [프로그래머스] 게임 맵 최단거리
• 문제 링크: [https://school.programmers.co.kr/learn/courses/30/lessons/1844]
• 알고리즘 분류: DFS/BFS

풀이 과정

BFS를 활용하여 visited를 하나씩 늘리면서 경로를 이동하면 목적지까지의 최단 경로를 찾을 수 있다.

1 문제 분석 및 제약 조건 확인

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수

• n과 m이 모두 1인 경우는 입력으로 주어지지 않음

• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리

2 알고리즘 및 자료구조 선택

BFS

3 절차적 구현 흐름

visited배열을 -1로 초기화, (0,0)은 1로 설정해주고 BFS를 진행하며 queue에 쌓이는 좌표를 (sy, sx)의 visited 값 +1 해주면 도착지의 최솟값을 구할 수 있다.

4 시간 복잡도

O(N*M)