알고리즘/BFS , DFS 알고리즘 (2) 썸네일형 리스트형 DFS (Depth First Search)(깊이 우선 탐색) DFS란 다음 분기로 넘어가기전에 해당 분기를 모두 탐색하는 탐색 방법입니다. 즉 임의의 노드에서 갈수있는 만큼 깊게 들어간 후 더 이상 진행할 수 없으면 그전으로 다시 돌아가 탐색을 시작합니다. 1을 시작으로 DFS 탐색을 한다면 1-2-3-6-7-4-5 이런 식으로 탐색이 진행됩니다. (인접해있는 노드 중 작은 노드부터 탐색한다고 가정했을 때) 물론 정확한 탐색순서는 저장되어있는 노드 순서에 따라 다르지만, 중요한 것은 하나의 노드로부터 가장 깊게까지 탐색을 하고 막히게 되면 그전으로 돌아가 다시 탐색을 진행한다는 것입니다. BFS는 큐를 사용하지만 DFS는 스택을 사용하여 쉽게 구현할 수 있습니다. 하지만 굳이 스택 STL을 이용하지 않고 재귀함수를 이용하면 편합니다. (재귀함수 자체가 스택처럼 저.. BFS (Breath First Search)(너비 우선 탐색) BFS란 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법입니다. 즉 끝까지 깊게 먼저 탐색하는 dfs랑 대비됩니다. 1을 시작으로 bfs탐색을 한다면 (1)->(2->3)->(4->5->6->7) 이런 식으로 탐색을 합니다. 괄호를 친부분은 같은 거리를 표시한 것 입니다. 즉 괄호 안에서의 탐색 순서는 큐에 넣은 순서에 따라 달라지기 때문에 코드에 따라 달라질 수 있습니다. 그래프는 vector를 이용하면 쉽게 표현 할 수 있습니다. 위의 그래프는 아래와 같이 표현됩니다. a[1].push_back(2); //노드 1에서 노드 2로 연결 a[1].push_back(3); a[2].push_back(1); a[2].push_back(3); a[2].push_back(4); a[2].push_back(5).. 이전 1 다음
