[백준]BOJ_2178_미로 탐색_S1

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

위 문제는 전형적인 BFS 알고리즘, 넓이 우선 탐색 알고리즘을 이용한 문제이다.

최단거리, 최적경로와 같은 촤단, 최적이라는 단어가 쓰이면 BFS 알고리즘을 사용한다고 생각하자.

BFS 알고리즘은 넓이 우선 탐색으로 노드로 트리를 구성한다고 했을때 트리의 높이, 트리의 레벨이 경로의 길이가 된다.

넖이 우선 탐색은 트리로 그려지고 트리로 그린 것을 큐로 넣었다가 빼면서 간선을 이어갈 수 있다.
넓이 우선 탐색에서 큐를 그리면서 이해할 수도 있지만 가장 간단하게 시각화 해볼 수 있는건 와이파이이다.
동일 선상에 있는 노드들은 출발 노드인 루트로부터 같은 거리에 있는 것이다.

여기서 큐를 사용해서 BFS를 진행할 경우에 주의사항은 큐에 들어가있는 것이 전부 나와야 종료가 된다는 것이다.
즉, 도착지에 도달해도 큐에 무언가가 있으면 실행이되고, 그렇게 되면 도착지에 더 멀리 돌아서 도차가는 거리가 출력이 된다. 예제 입력 4와 같은 아래와 같은 미로가 주어지면 최단 경로는 "ㄴ"  형태로 9가되고 종료가 되어야하지만, 멀리 돌아가는 길이 큐에 남아있어 11이 출력되게 된다. 

O	X	O	O	O
O	O	O	X	O
O	X	X	X	O
O	X	X	X	O
O	O	O	O	O

 이를 막아주기 위해 flag를 사용하여 도착지가 출력되면 종료되게 하였다.