[알고리즘][BFS] 미로 탐색 (백준)

BFS 알고리즘 문제 : 미로 탐색 (백준)

약 2주전 이 문제를 DFS 알고리즘으로 풀어본 적이 있다.

하지만 시간초과가 떠서 상당히 난감한 적이 있었는데

이를 BFS 알고리즘으로 풀어보니 상당히 쉽게 풀렸다.

해가 없는 경로로도 쭉쭉 들어가서 수행시간을 폭발 시키는 DFS 알고리즘의 단점을 실감할 수 있었고,

DFS 알고리즘에 비해 BFS 알고리즘은 공간 복잡도는 상당하지만 항상 최단 경로를 보장한다는 장점을 체험할 수 있었다.

미로 탐색이라는 알고리즘은 DFS, BFS 알고리즘으로 풀어봄으로써

약간씩 헷갈렸던 두 알고리즘의 장단점을 명확하게 할 수 있었다.

미로 탐색 (백준)

1. 필요한 변수 선언

2. 초기화

3. 인큐, 디큐, 비었는지 확인, 가능한 경로인지 확인

4. BFS 알고리즘

5. 메인

6. 참고

DFS 알고리즘과 BFS 알고리즘의 장단점을 잘 정리해놓은 것 같아 링크를 가져왔다.

http://blog.naver.com/jjuncoder/220797012420