DFS (3) 썸네일형 리스트형 백트래킹(BackTracking)이란? Q. 백트래킹이란 ? 지금은 네비게이션이 잘 발달 되어 있으니 설명이 애매하지만 네비게이션도 없고 지도도 없는 세상에 왔다. A출발점에서 B 목적지까지 아무것도 없이 걸어서 또는 자전거를 타고 여행을 간다고 생각하면 일단 직관적으로 아 이쪽길로 가면 목적지에 가겠지 하고 가본다. 그런데 도착해서 동네사람들에게 물어보니 이동네는 그 동네가 아니라고 하면 선택은 다른 갈림길로 가던지 일단 왔던길을 되돌아가서 이쪽길은 절대가면 안되는길이라고 뭔가 표식을 달아 놓고 다른 길로 가는 선택을 할 수 있겠다. 물론 길을 선택하는데 앞에 강이 있거나 큰 바다가 있거나 높은 산이 있거나(제약조건) 등... 어떠한 이유로 갈수없는것들은 목숨걸고 갈필요 없이 포기하고 빨리 다른길을 선택 할 수도있다. 이리저리 이길 저길 다.. [그래프] 위상 정렬(Topological Sort) - Kahn's algorithm 방향 비싸이클 그래프(DAG, Directed Acyclic Graph) 는 보통 작업간의 우선순위를 표현하는 용도로 사용된다고 했다. 그런데 그래프에서 작업들을 어떤 순서로 해야하는지 알아야 하는데 어떻게 할 수 있을까 ? 예를들어 아래와 같은 DAG 가 있고 7부터 작업을 시작한다면 7 다음에 5를 할지 6을 할지 그 순서를 정해야 한다. 이와 같이 일어나야 할 순서에 따라 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬(Topoligical Sort)을 이용할 수 있다. 그림 1)을 위상정렬 하면 그 순서는 7 6 5 4 3 2 1 0로 출력된다. 그럼 실제로 정렬시 작업이 우선순위에 맞는지 즉, 유효한 순서가 되기 위해서 어떤 조건을 만족해야 할까? 당연한 건데 작업의 순서는 .. 그래프(Graph)-깊이우선탐색(DFS, Depth First Search) 그래프를 순회하기위한 방법중 너비우선탐색(BFS, Breadth First Search) 은 알아봤고 이번에는 깊이우선탐색(DFS, Depth First Search)알고리즘을 살펴보자. 깊이우선탐색(DFS, Depth First Search)은 이진트리의 전위순회(pre order)과 비슷한 개념이고 재귀나 스택(Statck)를 이용하여 알고리즘을 구현할 수 있다. △ [출처] https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm 위에서 주어진 예제에서와 같이 DFS 알고리즘은 S에서 A에서 D로 G에서 E에서 B로, F에서 마지막으로 C로 이동한다. DFS를 스택를 이용하여 구현할 수 있다고 하였는데 코드.. 이전 1 다음
