728x90 너비우선탐색1 [C++] DFS(Depth First Search), BFS(Breath First Search) 개념 깊이 우선 탐색(Depth First Search) 루트 노드를 시작으로 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색하는 탐색 방법 예시코드 void dfs(int x){ if(check[x]) return;//방문한 곳인지 체크 check[x] = true; for(int i = 0; i < a[x].size(); i++){ int nx = a[x][i]; dfs(nx); } } 장점 - 단지 현 경로상의 노드들만 기억하면 되기 때문에 저장 공간의 수요가 적습니다다. - 목표노드가 깊은 단계에 있는 경우에 빠르게 구할 수 있습니다. 단점 - 해가 없는 경로에 깊이 빠질 가능성이 있습니다. - 얻어진 해가 최단 경로를 통해 얻어진다는 보장이 없습니다. (위의 이미지에서 구해야 하는 해는 2번인.. 2021. 8. 23. 이전 1 다음 728x90
