목차
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
예제
입력
7
1 6
6 3
3 5
4 1
2 4
4 7
Plain Text
복사
출력
4
6
1
3
1
4
Plain Text
복사
예제2
입력
12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12
Plain Text
복사
출력
1
1
2
3
3
4
4
5
5
6
6
Plain Text
복사
풀이
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000) # 재귀 횟수 늘려주기
N = int(input())
Tree = [[] for _ in range(N+1)] # 연결된 트리 리스트
parent = [0]*N # 부모 node 리스트
# 부모 노드에 대한 정보 없이 일단은 Tree 쌓기
for _ in range(N-1):
a, b = map(int, input().split())
Tree[a].append(b)
Tree[b].append(a)
# 부모 Node 찾기
def parent_finder(root, Tree, parent):
for i in Tree[root]: # root와 연결되어 있는 node들을 하나씩 살펴보자.
if parent[i-1] == 0: # 만약 그 노드들의 parent가 없다면,
parent[i-1] = root # 그 노드들의 parent는 현재 root임.
parent_finder(i, Tree, parent) # 그리고 그 노드와 연결되어있는 노드들의 부모 노드를 또 찾아주자.
parent_finder(1, Tree, parent)
for i in range(1, N):
print(parent[i])
Python
복사
문제의 포인트는 우선 Tree를 쌓고, 부모 Node를 순서대로 찾아주는 것이다.
•
parent_finder
→ 노드 i와 j가 있을 때 i는 j의 부모이거나 j는 i의 부모라는 것을 이용한다.
만약 i가 j가 아닌 다른 부모를 가지고 있을 때, 무조건 j의 부모는 i이다. 왜냐하면 j가 i의 부모가 아니므로 i는 j의 부모가 되기 때문이다.
parent_finder는 node 1과 연결되어있는 노드들부터 살펴보기 시작한다. 그런데, node 1은 루트로 지정되어 있기 때문에(문제 조건) node 1과 연결되어 있는 노드들은 무조건 1을 부모로 갖는다. 따라서 1을 부모로 지정해준다: parent[i-1] = root
그 다음 1을 부모로 갖는 노드들(node with parent 1 이라 하자)과 연결 되어 있는 노드들은 1을 제외하고는 node with parent 1이 무조건 부모이다. 따라서 그들의 부모를 node with parent 1으로 설정해준다. 그리고 또 자식 노드들의 부모를 설정해준다. 이런식으로 재귀적으로 문제를 푸는 것이 핵심.
정리하자면
•
Node 1과 연결되어 있는 노드들 중 부모 노드가 없는 노드들을 주목한다.
•
해당 노드들의 부모를 1로 설정한다.
•
반복
•
Node 1부터 시작
해당 문제는 무조건 root를 1로 시작해야 풀린다.
만약 root를 다른 node로 잡았다고 하자. 예를 들어 3으로 잡았고 연결되어있는 노드들이 6과 5라고 해보자. 그럼 이때 부모 노드가 이미 존재하는지를 판단하고 부모 자식 관계를 설정해야 하는데, 판단할 수 있는 근거가 없다. 따라서 root인 1부터 시작해서 차례로 내려가야 한다. 즉, 해당 방식은 깊이 우선 탐색(dfs, depth-first-search) 방식이다.
기억할 점
•
Tree 문제에서는 링크된 노드들에 대한 정보를 담는 list와 부모 노드에 대한 정보를 담는 list 두 개로 나누어서 문제를 진행한다.
•
재귀 문제를 풀 때 재귀 횟수에 한계가 정해져 있으므로 sys.setrecursionlimit(1000000)를 통해서 재귀 횟수를 늘려준다.
•
i와 j가 링크되어 있을 때 i는 j의 부모이거나 j는 i의 부모이다.