트리(유형정리) - 백준 11725

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

 

문제는 간단한데 입력받은 숫자들에서 1이 가장 루트 노드이다.

 

그렇다면

1->6->3->5

1->4->2

     4->7

 

이렇게 깊이 4의 트리가 만들어지게 된다. 처음에는 앞이 부모, 뒤가 자식 노드라고 생각했는데 그러면 그림이 좀 이상해지고 1이 루트노드가 될 수 없게 된다.

 

문제를 보고 트리를 어떻게 짜는 것인지 전혀 감이 잡히지 않았다. 트리 문제는 코딩테스트로 처음 풀어보는 것이어서...

구글링을 해보니 DFS와 BFS를 활용한다. 그래프 이론을 트리에서도 활용한다는 것이 핵심!!!

 

자 그럼 문제를 풀어보자.

 

※ 알고리즘

1. N을 입력받고, DFS를 구현해줄 visited리스트와 정답을 담을 result리스트를 빈 리스트로 구현해준다.

2. node를 빈 리스트로 N+1개 만들어서 담아준다.(노드 별로 독립적인 리스트를 가지게 해야한다는 것이 핵심!!!)

3. 부모와 자식을 입력받는데, 여기서 parents와 child가 반드시 두 개의 값을 반환하지 않으면 ValueError가 발생하므로 예외처리를 시켜준다.

4. DFS를 stack을 사용하여 구현해준다.

5. DFS를 1부터 호출시켜주고 result에 담아서 출력시킨다.

 

 

from collections import deque
import sys

input = sys.stdin.readline
N = int(input())
visited = [0]*(N+1)
result = [0]*(N+1)

node = list([] for _ in range(N+1))
for i in range(N-1):
    while True:
        try:
            parents, child = map(int, input().split())
            break
        except ValueError:
            print("Please enter two values separated by a space.")
    node[parents].append(child)
    node[child].append(parents)

def DFS(node, v, visited):
    visited[v] = True
    stack=deque([v])
    while stack:
        w = stack.pop()
        for i in node[w]:
            if not visited[i]:
                stack.append(i)
                visited[i] = True
                result[i] = w

DFS(node, 1, visited)
for i in range(2, N+1):
    print(result[i])

 

이 문제에서 처음에는 node를 반복적으로 빈 리스트에 빈 리스트를 append 하는 식으로 구현했다. 그렇지만 이렇게 구현하게 되면 모든 노드가 동일한 빈 리스트를 공유하게 되어 한 노드에 연결된 노드를 추가하면 모든 노드에 그 연결정보가 추가되게 된다. 노드 별로 독립적인 리스트를 트리는 가져야 하므로

node = list([] for _ in range(N+1))

 

이렇게 정답을 얻을 수 있었다!!!