//20180111 Starbucks
//use Queue
BFS문제가 어떤게 있는지 잘 몰라서 백준사이트에 들어가서 BFS항목을 클릭헀다.
제일 위에 미로탐색이 있어서 풀어보았는데
알고리즘을 생각해보니 DFS였다. 재귀적으로...
난 이걸 풀면서 BFS인줄 알았다.
Test Case를 통과하고 제출했는데 시간초과가 떴다.
뭐지? 하는 마음에 '미로탐색 BFS' 라고 검색해보니
DFS로도 풀 수 있는데 DFS로는 시간초과가 걸리는 문제였다.
분명히 예전에는 BFS로 풀었던 것 같은데 헷갈려서..
그래서 BFS를 곱씹고자 글을 남긴다.
다음과 같은 미로가 있다.
array[0][0]부터 array[n][m]까지의 최단경로를 구한다고 하면
110110 110110 111111 111101
배열을 하나 더 만들어서 경로를 저장해준다.
120890
230780
345678
456709 이렇게된다.
발생시점은 1-2-3-4-5-6-7-8-9 이다. 큐를 이용하면 BFS를 구현할 수 있다.
while(queue.isEmpty()) 돌리면 된다.
1에서의 Next(2)를 큐에 넣고, 2에서의 Next(3)를 큐에넣고....
DFS와 다른점은 Distence를 배열로 해야 한다는 점이다.
또한 한번 방문한곳은 재방문하지 않는다.
