[Algorithm] BFS - ‘미로 탈출 문제’

📣 학습한 내용을 정리한 글입니다.

BFS 알고리즘 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

영준이는 N x M 크기의 직사각형 형태의 미로에 갇혔다. 영준이의 위치는 (1, 1)이며, 미로의 출구는 (N, M)이다.
이때 괴물이 있는 부분은 ‘0’이고 괴물이 없는 부분은 ‘1’이다. 이때 영준이가 탈출하기 위해 움직여야하는 최소 칸의 개수는?
(단 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.)

입력

첫 번째 줄에 두 정수 N, M이 입력된다. (4 <= N, M <= 200)
두 번째 줄부터 N+1개 줄 까지 각각 M개의 정수(0 or 1)의 미로 정보가 입력된다.
(각각 수들은 공백없이 입력되며, 시작 칸과 마지막 칸은 항상 1이다.)

출력

첫째 줄에 이동 칸의 개수를 출력한다.

문제 풀이

---

BFS Algorithm 참고내용

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
  
• Queue 자료구조를 이용한다.
  

위 참고사항을 준수하며, 풀어보자.
일단 시작지점부터 가까운 노드들 순으로 탐색하여 ‘1’인 지점을 찾는다.
상, 하, 좌, 우로 이동가능하며 ‘1’인 지점을 찾음 과 동시에 노드의 최단거리 값을 기록해나가면 해결할 수 있다.
마지막 탈출 지점의 최단거리를 출력하면 결과값을 도출해낼 수 있다.

작성 코드

Python

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 3. DFS & BFS 영상

---