KEEP GOING!

이번 포스팅에서는 알고리즘을 공부하면서 출제 빈도가 높은 BFS와 DFS 문제를 위한 기본 구현을 정리하려고 한다. BFS와 DFS는 이름에서부터 알 수 있듯 그래프 탐색 알고리즘이다. 탐색 알고리즘은 그래프 전체를 순회해야 하는 고비용 연산으로 효율적으로 코드를 짜는 것이 중요하다. BFS와 DFS 모두 시간 복잡도는 동일하다. 그래프는 인접 행렬과 인접 리스트 자료구조를 이용해 표현이 가능한데, 어떤 자료구조를 사용하느냐에 따라 시간 복잡도가 아래와 같이 달라진다. (V = Vertex, E = Edge) 인접 행렬: O(V^2) 인접 리스트: O(V+E) 최소 비용 문제나 이동에 가중치가 없는 미로탐색 문제는 BFS로 푸는 것이 유리하고, 이동에 제약이 있거나 이동마다 가중치가 붙는 미로탐색 문제는..