목록그래프 이론 (1)

Doby's Lab

[알고리즘] 백준 2178번: 미로탐색(C++), DFS와 BFS의 차이

이번 문제는 DFS를 활용하여 풀려했었다. 하지만, DFS로 구현할 경우에는 TLE가 발생한다. 게시판에서는 BFS를 활용하여 풀어야 한다고 조언한다. 문제를 풀 때 어떤 포인트에서 DFS 혹은 BFS로 풀어야 하는지 알 수 있을까? 여러 블로그를 읽어보다가 감이 잡힌 듯하다. 최단 경로를 알아보아야 할 때, BFS BFS는 어떤 기준점으로부터 인접한 노드들을 차근차근 접근 해나가지만 DFS는 한 군데 길로 쭉 갔다가 조건을 만족하지 못하면 다시 돌아와 다른 노드들을 접근하기 때문에 시간적인 측면에서 BFS가 이런 부분에서는 효율적이다. 하지만, 경로에 대해 가중치(weight)가 붙을 때는 DFS를 활용해야 한다. 이동 과정에 있어서 여러 제약이 있을 때는 DFS (이 점에서 백트래킹과 유사한 거 같다..
PS/BOJ 2021. 10. 5. 00:07
이전 Prev 1 Next 다음