목록- (1)
새벽의 블로그
< DFS(깊이 우선 탐색) BFS(넓이 우선 탐색) >
*정석 이론dfs는 stack을 사용한다. 재귀적 방법이다..- 방문한 노드의인접 노드 중 가장 가까운 노드(보통 숫자가 작은 노드)를 stack에 넣고 방문한다.- 그 방문 노드의 인접 노드 중 가장 가까운 노드(보통 숫자가 작은 노드)를 stack에 넣고 또 방문한다.- 방문할 인접 노드가 없다면 (=leaf에 다다른 것이다) stack에 넣어놨던 노드를 꺼내어 반복한다. (가장 최근에 들어간 노드가 나오므로, 그 부모 노드가 나와서 거꾸로 거슬러 올라갈 수 있다.) bfs는 queue를 사용한다. - 방문한 노드의 모든 인접 노드를 queue에 삽입한다.- queue에서 다음노드를 꺼내어 다시 모든 인접 노드를 탐색한다.- 방문할 노드가 없을 때까지 반복한다. *그래프-노드 표현은 인접그래프, 인접..
Algorithm/solution
2024. 5. 15. 03:30