[자료구조론]Queue를 이용한 미로찾기 과제

1. 문제정의

미로찾기는 컴퓨터 과학에서 자주 다루어지는 문제 중 하나로, 주어진 미로에서 시작 지점에서 목표 지점까지의 경로를 찾는 과정을 말한다. 미로는 일반적으로 2차원 격자로 구성되어 있으며, 각 격자는 이동할 수 있는 경로 또는 이동할 수 없는 장애물로 구분된다. 이 문제는 다양한 분야에서 활용될 수 있으며, 로봇 공학, 게임 프로그래밍, 경로 최적화 등 여러 분야에서 그 중요성이 강조된다. 특히, 미로찾기 과제를 통해서는 알고리즘적 사고를 기를 수 있으며, 데이터 구조의 활용을 통해 효율적인 문제 해결 방법을 익힐 수 있는 기회를 제공한다. 문제의 본질은 시작 점에서 목표 점까지의 유효한 경로를 찾는 것이다. 이 과정에서는 여러 경로가 있을 수 있으며, 최단 경로를 찾는 것이 경우에 따라 요구될 수 있다. 따라서, 미로를 탐색하는 과정에서는 어떤 알고리즘을 사용하여 이 문제를 해결할 것인가가 중요한 문제로 떠오른다. 여러 가지 탐색 알고리즘이 존재하지만, 여기서 Queue 자료구조를 이용한 너비 우선 탐색(BFS, Breadth-First Search) 방법을 통해 미로를 탐색하는 방식이 주목받는다. Queue는 선입선출(FIFO, First-In-First-O…(생략)