[백준] 11725번 트리의 부모 찾기 (트리 문제)

사용 언어 - Python3, PyPy3

문제 -  11725번 트리의 부모 찾기

트리 = Tree = 나무 = Root + Seed

족보(가족관계도) = 조상 + 자손

 

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

 

정답

트리의 조건

1. 모든 노드들은 연결되어 있어야 한다. (1개도 트리 가능)

2. 사이클이 발생하면 안된다. (내 아들이 할아버지이다? 불가능)

 

트리의 종류

1. 조상이 정해진 트리 = 루티드 트리

2. 조상이 정해지지 않은 트리 = 트리

 

 

 

 

1. 양방향

누가 부모이고 누가 자식인지 모르기 때문에 양방향으로 트리를 연결해준다.

 

2. 부모 = 이전에 방문한 노드값

parent[node] = prv = 현재의 노드의 부모는 이전에 방문한 노드

다음 방문할 노드가 양방향이기 때문에 역주행 할 수 있다. 그러므로 nxt == prv를 통해 새로 방문할 노드가 이전의 노드와 같다면 무시해준다.

 

3. 재귀함수

recur(node, prv)

recur(nxt,node)

import sys
sys.setrecursionlimit(99999)

def recur(node, prv):
    parent[node] = prv # 해당 노드의 부모 = 이전 노드
    for nxt in tree[node]:
        if nxt == prv: # 역주행 방지, 재계산 금지
            continue
        recur(nxt, node)
    
n = int(input()) # 노드 개수
tree = [[] for _ in range(n+1)]
parent = [0 for _ in range(n+1)]

for _ in range(n-1): # 간선의 개수 = n-1
    a, b = map(int,input().split()) # 정점1, 정점2
    # 양방향 = 누가 부모이고 자식인지 모르기 때문이다.
    tree[a].append(b)
    tree[b].append(a)

recur(1,0)
for answer in parent[2:]:
    print(answer)

 

 

 

추가 공부 !!!

자식을 알고 싶은 경우

깊이 알고 싶은 경우

자식들의 숫자 알고 싶은 경우

 

1. 새로운 리스트 생성

child = [[] for _ in range(n+1)] # 자식
depth = [0 for _ in range(n+1)] # 깊이
child_num = [1 for _ in range(n+1)] # 자식수

 

2. 관계 설정

child[prv].append(node) #  이전 노드의 자식 = node 노드

child[node].append(nxt) # 자식노드 node의 자식 = nxt

depth[nxt] = depth[node] + 1 # 깊이 한개씩 추가

child_num[node]  += child_num[nxt] # 자식수

 

import sys
sys.setrecursionlimit(99999)

def recur(node, prv):
    parent[node] = prv # 해당 노드의 부모 = 이전 노드
    child[prv].append(node)
    
    for nxt in tree[node]:
        if nxt == prv: # 역주행 방지, 재계산 금지
            continue
        
        child[node].append(nxt) # 자식노드
        depth[nxt] = depth[node] + 1 # 깊이
        
        recur(nxt, node) # 자식에게 이동
        
        child_num[node] += child_num[nxt] # 자식 수
        
    
n = int(input()) # 노드 개수
tree = [[] for _ in range(n+1)]
parent = [0 for _ in range(n+1)] # 부모
child = [[] for _ in range(n+1)] # 자식
depth = [0 for _ in range(n+1)] # 깊이
child_num = [1 for _ in range(n+1)] # 자식수


for _ in range(n-1): # 간선의 개수 = n-1
    a, b = map(int,input().split()) # 정점1, 정점2
    # 양방향 = 누가 부모이고 자식인지 모르기 때문이다.
    tree[a].append(b)
    tree[b].append(a)

recur(1,0)

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/11725_%ED%8A%B8%EB%A6%AC%EC%9D%98%EB%B6%80%EB%AA%A8%EC%B0%BE%EA%B8%B0.py