[Algorithm] DFS (Depth First Search)

1. DFS란?

깊이 우선 탐색(DFS)는 의미 그대로 깊이를 우선으로 하여 탐색하는 것이다. 자세히 얘기하자면, 루트 노드에서 시작해서 자식 노드로 이동한다 (보통 왼쪽 노드로 이동한다). 이동한 자식 노드에서 다시 자식 노드로 이동한다. 이 과정을 자식 노드가 없을 때까지 (리프 노드에 갈 때까지) 반복한다. 리프 노드에 도달하면, 리프 노드의 부모 노드로 가서 다시 오른쪽 자식을 방문한다. 오른쪽 자식에서 위에서 했던 과정을 반복한다. 이 재귀적인 방문을 탐방이라고 하겠다. 이렇게 모든 노드를 방문할 때까지 탐방을 완료하면 search가 끝난다. 

 

그래프를 예를 들어보자.

 

예제 그래프

 

위와 같은 그래프가 있다고 할때, 깊이 우선 탐색으로 탐색해보자. 루트에서 왼쪽으로 계속 이동하며 리프 노드가 나올 때까지 가므로 처음엔 9 > 8 > 5 순으로 이동할 것이다. 리프 노드에 도달했으므로 부모 노드로 돌아가서 오른쪽 자식을 다시 탐방한다(부모 노드로 돌아가는 것은 순서에 넣지 않는다). 따라서 9 > 8 > 5 > 2 로 이동할 것이다. 마찬가지로 리프 노드이므로 부모 노드로 돌아가고, 모든 자식을 방문했으므로 다시 위로 올라간다. 이후 6 > 1 순으로 탐방한다. 따라서 최종 순서는 9 > 8 > 5 > 2 > 6 > 1이 될 것이다.

 

구현에는 스택을 쓴다. 리프 노드에서 부모 노드로 돌아갈 때를 생각해보자. 위의 예제에서, 9 > 8 > 5로 이동했으므로, 8로 방문해야 한다. 따라서 방문했다는 의미로 5를 빼고 나면, 그 직전에 들어간 노드인 8을 빼서 8의 자식을 다시 방문해야 한다. 이러한 연유로 스택을 사용하여 구현한다. 

 

2. 구현

 

이진 트리에서의 DFS 코드이다. 이진 트리를 배열로 나타내는 방법은 다음 링크를 참고하자.

https://codinglilly.tistory.com/16

[Algorithm] Heap Sort (힙 정렬)

n = int(input())
graph = list(map(int, input().split()))
stack = [0]
visited = [-1 for _ in range(n)]
res = []

while len(res) != len(graph):
    print(stack, res)
    present = stack.pop()
    left = 2 * present + 1
    right = 2 * present + 2

    if visited[present] == -1:
        res.append(graph[present])
        stack.append(present)
        visited[present] += 1

    if left < n or right < n:
        if visited[left] == -1 and left < n:
            stack.append(left)
        elif visited[right] == -1 and right < n:
            stack.append(right)
print(res)

left를 먼저 검사하는 특성을 위해 elif 문을 넣어주었다. 방문한 적이 없는 노드가 present가 되면 res, visited를 갱신한다.

이후 왼쪽, 오른쪽 자식을 검사하여 방문한 적이 없으면 다음 차례에서 방문하기 위해 stack에 append한다.