코딩테스트/알고리즘
[알고리즘] DFS & BFS - 깊이우선 탐색과 너비우선 탐색
:: 그래프 탐색 :: dfs와 bfs알고리즘은 대표적인 그래프 탐색 알고리즘이다. 해당 알고리즘은 코딩 테스트에 높은 비율로 출제되기 때문에 꼭 학습해야하는 알고리즘 중 하나이다. DFS(Depth First Search) - 깊이 우선 탐색 깊이 우선 탐색은 재귀를 통하여, 시작 노드부터 그래프의 제일 안쪽 노드까지 깊숙히 방문하며 그래프를 탐색하는 알고리즘이다. 다음 그림 예시를 통해 탐색과정에 대하여 알아보자 1번에서 시작하는 다음과 같은 그래프가 있다고 하자. 그래프는 수가 작은 순으로 탐색하도록 초기 값이 주어진다. 그럼 DFS로 탐색하게 되었을 때, 어떻게 탐색하게 될까? 노드에 방문할 때마다 해당 노드에 방문 처리를 하며, 1과 연결되어 있는 노드2와 노드3 중에 수가 작은 순으로 탐색을 ..
