백준(11725,1068,1991)

트리(BinaryTree)

백준(11725, 1068,1991)

트리의부모찾기(11725)

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

• 입력

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

• 입출력 예시

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

--------------

4
6
1
3
1
4

해결책

노드의 오름차순으로 루트부터 하위노드로 가기때문에, 1번노드에서 그래프탐색(DFS, BFS)를 진행하면 쉽게해결할 수 있다.

각 연결정보는 인접리스트로 양방향으로 정의한다.

코드

import sys
sys.setrecursionlimit(10**6)
input =sys.stdin.readline

n = int(input())

parent = [0]*(n+1)
visited=[0]*(n+1)
maps= [[] for _ in range(n+1)]

def dfs(n):
    global maps,parent,visited
   
    visited[n]=1

    for node in maps[n]:
        if not visited[node]:
            parent[node]=n
            dfs(node)

for i in range(n-1):
    a,b=map(int,input().split())
    maps[a].append(b)
    maps[b].append(a)

dfs(1)

for i in range(2,n+1):
    print(parent[i])

리프노드의 개수 구하기(1068)

트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.

예를 들어, 다음과 같은 트리가 있다고 하자.

현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.

이제 리프 노드의 개수는 1개이다.

• 입력

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다.

• 입출력 예시

5
-1 0 0 1 1
2

--------------

2

해결책

이문제 역시 단순 그래프탐색으로 해결할 수 있다.

하지만 문제는 n번노드를 삭제한다면 그아래의 하위노드들이 다 삭제된다는 것인데, 단순하게 삭제해야하는 노드가 하위노드이면 append를 시켜주지 않든, 재귀호출을 진행하지 않으면 해결 할 수 있다.

코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
ls=list(map(int,input().split()))
delnode = int(input())
maps=[[] for _ in range(n)]
visited=[0]*(n)
ans=0

def dfs(n):
    global visited,ans
    visited[n]=1
    cnt=0
    for node in maps[n]:
        if not visited[node] and delnode!=node:
            cnt+=1
            dfs(node)
    if cnt==0 :
        ans+=1
            

start=999
for i in range(0,n):
    if ls[i]==-1:
        start = i
        continue
    maps[ls[i]].append(i)
    maps[i].append(ls[i])

if delnode == start :
    print(ans)
else :
    dfs(start)

    print(ans)

트리순회하기(1991)

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

• 입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

• 입출력 예시

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

#.은 연결x를 의미한다.
--------------

ABDCEFG
DBAECFG
DBEGFCA

해결책

이 또한 그래프 탐색으로 쉽게 해결할 수 있다. 이진트리를 표현하는데 있어서 다양한 방법이 존재하지만, 간단히 딕셔너리를 선언해서 표현하고, 문제의 설명과 같이 dfs를 구성해주면된다.

• 전위: root출력→왼쪽노드 호출→오른쪽노드호출
• 중위:왼쪽노드 호출 → root출력 → 오른쪽노드호출
• 후위:왼쪽노드호출 → 오른쪽노드호출 → root출력

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())

tree = {}

for i in range(n):
    node, start, end=map(str,input().split())
    tree[node]=[start,end]

def preorder(n):
    global tree
    if n == '.':
        return 

    print(n,end="")
    preorder(tree[n][0])
    preorder(tree[n][1])
    
def inorder(n):
    global tree
    if n == '.':
        return  
    inorder(tree[n][0])
    print(n,end="")
    inorder(tree[n][1])
    
def postorder(n):
    global tree
    if n == '.':
        return 
    postorder(tree[n][0])
    
    postorder(tree[n][1])
    print(n,end="")

preorder('A')
print()
inorder('A')
print()
postorder('A')