🗺️ 미로 탈출 알고리즘

🛤️ 찾은 경로

경로: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (3,2) → (3,3) → (3,4) → (3,5) → (4,5) → (5,5) → (5,6) → (6,6) → (7,6) → (7,7) → (7,8) → (7,9)

총 이동 횟수: 16회

🧠 BFS 알고리즘 설명

1. 미로 생성: 시작점(0,0)과 끝점은 항상 true로 설정하고, 나머지는 70% 확률로 길을 생성

2. 경로 탐색: BFS(너비 우선 탐색) 알고리즘을 사용하여 최단 경로 탐색

3. 큐 활용: FIFO 구조로 가까운 거리부터 차례대로 탐색

4. 최적화: BFS는 가중치가 없는 그래프에서 최단 경로를 보장

5. 방문 체크: 중복 방문을 방지하여 효율성 증대

🔍 동작 과정

1. 시작점 (0,0)을 큐에 추가하고 방문 표시
2. 큐에서 노드를 꺼내어 목표점인지 확인
3. 4방향(상하좌우) 인접 칸을 확인
4. 갈 수 있고 방문하지 않은 칸을 큐에 추가
5. 목표점 발견하거나 큐가 빌 때까지 반복

⏱️ 시간 복잡도

O(V + E) - V: 노드 수, E: 간선 수 (미로에서는 O(가로 × 세로))