나만의 개발노트

Backtracking*상태 공간 트리에서 DFS를 수행하여 promissing 노드만 탐색한다.non-promissing한 노드는 가지치기(pruning)하여 효율적으로 탐색한다 *상태 공간 트리(State Space Tree) 루트 노드부터 리프 노드까지의 경로가 후보 솔루션이 된다.non-promissing한 경로는 탐색하지 않고 부모 노드로 돌아가 다른 자식 노드를 탐색한다.void checknode(node v){ node u; if(promising(v)) //현재 노드(v)가 promising하다면, if(there is a solution at v) //v에서 결론이 나오면, 결론 반환 write the solution; ..

Depth-First Search (DFS): 트리 또는 그래프의 루트 노드를 먼저 방문하고, 그 후 자식 노드를 순서대로 방문한다.이 과정은 재귀적으로 진행된다.void depth_first_tree_search(node v){ node u; //자식 노드를 가르킬 노드 visit v; //v 노드에 방문했었는지 확인하는 변수 for(each child u of v) //v노드의 자식들 u를 모두 확인 depth_first_tree_search(u); //자식 노드 호출}

---키워드--- 1. 깊이 우선 탐색 (DFS) 2. 너비 우선 탐색 (BFS) * 정점(node) = N 간선(edge) = E 그래프를 탐색한다 = 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것. 1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 갈 곳이 없을 경우 옆으로 이동 깊이 우선 탐색(DFS, Depth-First Search) 너비 우선 탐색(BFS, Breath-First Search) :최대한 깊이 내려간 뒤, 더이상 갈 곳이 없을 경우 옆으로 이동 : 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동 1. 모든 노드를 방문하고자 하는 경우에 이 방법 2. 너비우선탐색(BFS)보다 좀 더 간..