안녕하세요 이번 시간에는 트리에 대해 알아보는 시간을 갖도록 하겠습니다.
트리란 노드와 간선으로 연결된 그래프의 특수한 형태입니다. 사이클을 가지고 있지 않으며 1개의 루트 노드가 존재합니다. 이 때 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가지며, 트리의 부분 트리 역시 트리의 모든 특징을 따른다는 특징이 있습니다.
트리는 인접 리스트 방식으로 구현합니다. 이 때 부모에서 자식, 자식에서 부모 모두 탐색할 수 있기 때문에 양방향 그래프로 설정해주어야 합니다. 트리 내의 노드의 탐색은 DFS를 이용하여 현재 노드부터 끝까지 탐색을 진행합니다.
백준 11725(트리의 부모 찾기) 문제의 경우 트리의 루트가 1이라고 할 때 각 노드의 부모를 구하는 문제입니다. 문제에서 주어진 노드 간의 연결관계를 인접 리스트로 구현한 후 DFS로 루느 노드에서부터 탐색을 시작합니다. 이 때 그래프에서 노드 내의 자식 노드들을 탐색하면서 아직 방문하지 않았을 경우 자식 노드의 부모 노드를 현재 노드로 설정한 후 다시 dfs를 진행합니다.
백준 1068(트리) 문제의 경우 주어진 트리에서 입력으로 주어진 노드를 지웠을 때 리프 노드의 개수를 출력하는 문제입니다. 11725 문제와 유사하게 인접 리스트로 트리를 구현한 후 DFS로 탐색하되 지우려는 노드를 DFS에서 탐색하지 않고 스킵합니다. 또한 하나의 노드의 자식 노드를 탐색하면서 자식 노드가 있을 경우 자식 노드 카운트를 하여 카운트값이 0일 경우 리프 노드이기 때문에 정답을 1 증가시킵니다.
