그래프이론1 [알고리즘 이론] 4. DFS, BFS DFS (Depth-First Search) 루트 노드(다른 임의의 노드도 가능)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색한다. 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. -> 재귀 or 스택 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부르 반드시 검사해야 한다. 이를 검사하지 않으면 무한루프에 빠질 수 있다. EX) visit[node] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더이상 갈 수 업게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하.. 2023. 5. 5. 이전 1 다음
