mondegreen

깊이우선탐색의 개념 1) 루트 노드(또는 임의의 노드)에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 직전의 갈림선이 있는 정점을 되돌아가야 하기 때문에 재귀적으로 구현하거나, 후입선출 구조의 스택을 활용 ; 시작 정점의 한 방향으로 갈 수 있는 가장 깊은 경로까지 탐색하다가 끝을 만나면 직전의 갈림선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 탐색하는 방법 깊이우선탐색의 특징 1) 자기 자신을 호출하는 순환 알고리즘의 형태이다. 2) 위와 같은 이유로 방문한 노드는 그 여부를 반드시 검사해야 무한 루프에 빠지지 않는다. 3) 전위 순회, 중위 순회, 후위 순회 모든 형태의 트리 순회는 모두 DFS의 한 종류이다. 4) 인접 행렬 또는 ..