경푸의 iOS 🍯

안녕하세요~ 오늘은 깊이 우선 탐색에 대해서 정리하려고 합니다. 깊이 우선 탐색( DFS, Depth-First Search )이란? 깊이 우선 탐색은 탐색하고자 하는 노드들의 자식 노드부터 우선으로 탐색하는 방식을 말합니다. 아래의 이미지에 있는 그래프에서 BFS를 사용하면 앞서 말한 것처럼 자식 노드부터 확인하는데 예를 들어서 1을 가장 먼저 탐색하고 나면 8, 6, 10, 7, 4 ... 을 순서대로 탐색하게 됩니다. 즉, 탐색하고자하는 노드의 자식 노드들을 모두 탐색하는 방법입니다. BFS와 마찬가지로 여기서 8부터 시작하든 2부터 시작하든 순서는 중요하지 않습니다. 중요한 점은 자식 노드들을 우선 탐색해야 한다는 것입니다. ✔︎ Swift로 구현해 보기 위의 이미지에 있는 그래프를 통해 DFS를..

안녕하세요~ 오늘은 너비 우선 탐색에 대해서 정리하려고 합니다. 너비 우선 탐색( BFS, Breadth-First Search )이란? 너비 우선 탐색은 인접한 노드들을 우선으로 탐색하는 방식을 말합니다. 아래의 이미지에 있는 그래프에서 BFS를 사용하면 앞서 말한 것처럼 인접한 노드부터 확인하게 되는데 예를 들어서 1을 가장 먼저 탐색하고 나면 인접한 8, 5, 2를 순서대로 탐색합니다. 다음은 6부터 시작해서 9까지 탐색을 진행하겠죠? 즉, 같은 레벨에 있는 노드들부터 탐색을 하는 것입니다. 여기서 8부터 시작하든 2부터 시작하 든 순서는 중요하지 않습니다. 중요한 점은 같은 레벨에 있는 노드를 전부 탐색하고 다음 레벨로 넘어간다는 것입니다. ✔︎ Swift로 구현해 보기 위의 이미지에 있는 그래프..