벽 부수고 이동하기는 변형된 BFS 문제입니다. BFS를 기반으로 문제를 풀어야 하지만 벽을 1회 부술 수 있다는 사실 때문에 단순 BFS에서 조금의 변형이 필요합니다. BFS는 이동할 수 있는 노드를 탐색하면서 중복된 탐색을 방지하기 위해 방문 여부를 표시하는 자료구조를 사용합니다. 한 노드에서 다른 노드로 가는 이동 조건이 모두 동일하다면 하나의 자료구조에 방문 여부를 표시하면 충분합니다. 하지만 이동 조건이 달라진다면 하나의 자료구조에서만 방문 여부를 표시하는 것을 문제를 해결할 수 있음을 보장하지 못합니다. 이동조건이 다르기 때문에 같은 노드를 뒤늦게 방문하여도 최단거리의 경로가 될 수도 있습니다. 따라서 하나의 자료구조에 대한 중복 조건 체크는 의미가 없으며 이동 조건의 수에 따라 방문 여부를 ..