[자료구조] 트리의 부모 찾기

트리의 속성을 완벽히 이해하기 위해 트리와 관련된 여러가지 문제들을 풀어보자. 이번에는 백준 11725 트리의 부모 찾기 문제를 통해 트리에서 루트 노드를 제외한 다른 노드의 부모 노드를 찾아보자.

---

접근

트리는 순환되지 않는 구조를 갖고있다. 그렇기 때문에 N개의 노드는 N-1개의 간선을 통해 트리를 구성할 수 있다. 만약 N-1개 보다 많은 간선을 갖는다면 순환되는 구조를 갖게된다.

 

이때 N-1개의 간선에 대한 정보(간선에 의해 연결된 두 개의 노드)가 입력으로 주어질 때 어떻게 저장하여 트리를 구현할 수 있을까? 이번에는 2차원 리스트를 활용하였다. a, b 노드를 입력받았을 때는 어떤 노드가 부모 노드이고 어떤 노드가 자식노드인지 알 수 없다. 따라서 a행의 리스트에 b를 추가하고 b행의 리스트에도 a를 추가한다.

 

위와 같이 트리를 표현하게 되면 각 행에는 자식 노드가 3개 이상이 존재할 수 있으며 부모 노드를 특정지을 수 없다. 하지만 문제에서 루트 노드를 1이라고 정했기 때문에 문제가 되지 않는다.

 

이제 DFS를 통해 각각의 노드에 대한 부모 노드를 찾아보자. 먼저 1번 노드를 방문한다. 이후 1번 노드에 포함된 자식 노드들을 탐색한다. 예를 들어 6번 노드가 1번 노드의 자식 노드에 포함되어있다면 6번 노드의 부모 노드로 1번 노드로 하고 6번 노드를 탐색한다. 이때 6번 노드의 자식 노드가 3번이라고 가정하고 1번 노드의 자식 노드도 3번이 온다면 방문 표시를 어떻게 해야할까? 라는 생각을 하게 되었다. 

 

위와 같은 생각으로 인해 6번 노드의 탐색을 모두 마치고 1번으로 돌아갔을 때 이미 3번 노드는 방문 표시가 되어 3번 노드의 부모 노드를 1번으로 할 수 없기 때문에 2차원 리스트에 저장하고 이처럼 DFS로 탐색해도 될까?라는 생각을 했지만 트리는 순환되지 않는 구조이며 위와 같은 입력이 주어진다면 트리라고 볼 수 없다. 따라서 트리의 부모 노드를 찾기위해 DFS를 활용할 수 있었다.

 

구현

이제 트리에서 각각의 노드에 대한 부모 노드를 Python으로 구현해보자.

• 노드의 개수를 입력받아 N에 저장한다.
• tree는 간선의 정보를 입력받았을 때 저장할 2차원 리스트이다.
• visited는 DFS를 실행했을 때 노드의 방문 표시를 하여 중복 탐색을 할 수 없도록 한다.
• parent는 DFS를 통해 찾은 부모 노드를 저장할 리스트이다.

N = int(input())
tree = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
parent = [0 for _ in range(N+1)]

 

• N-1개의 간선 정보를 입력받는다.
• 두 개의 노드에 대한 번호를 입력받아 아래와 같이 저장한다.

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

 

• 이제 DFS를 통해 부모 노드를 찾는다.
• 먼저 현재 방문한 노드에 대해 방문 표시를 진행한다.
• 이후 현재 방문한 노드의 자식 노드(next_node)를 탐색한다.
• 아직 방문하지않은 노드라면 해당 노드의 부모 노드는 현재 노드(node)가 된다.
• 다음에는 자식 노드를 DFS 인자로 전달하여 탐색을 계속한다.
• DFS를 통해 부모 노드를 찾을 수 있다.

def dfs(node):
    visited[node] = 1
    for next_node in tree[node]:
        if not visited[next_node]:
            parent[next_node] = node
            dfs(next_node)

---

정리

• 트리는 순환되지 않는 그래프이다.
• 따라서 N개의 노드가 있을 때 N-1개의 간선으로 트리가 구성되어있다.
• 트리의 부모를 찾기위해 DFS를 활용하였다.