🧚‍♂️알고리즘🧚‍♂️ - 트리🎄

🎄 트리 🎄

 노드와 에지로 연결된 그래프의 특이한 구조

 

- 사이클이 없다

-1개의 루트 노드가 존재한다

- 루트 노드를 제외한 노드는 단 1 개의 부모 노드를 가진다

+ 트리의 부분 트리는 트리의 모든 특징을 따른다

 

노드	데이터 표현 요소
에지	노드와 노드의 연결 관계를 나타내는 요소
루트 노드	트리에서 가장 상위에 위치한 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 위치한 노드
서브 트리	전체 트리에 속한 작은 트리

트리는 그래프 자료구조 중 하나의 형태이므로 그래프 구현/그래프 탐색 방식을 사용 가능

---

🥈 실버 2

11725번: 트리의 부모 찾기

1번(루트노드)부터 탐색하기

부모 노드의 값을 정답으로 출력

+ 양방향 에지로 인접 리스트 구현하기

 

DFS

import sys
sys.setrecursionlimit(10 ** 6)
N = int (sys.stdin.readline())
nearList = [[] for _ in range(N+1)]# 인접 노드 저장 리스트
visited = [False]*(N+1) # 모든 노드 방문했는지 확인
result = [0]*(N+1)

# DFS
def DFS(v):
   visited[v] = True 
   for i in nearList[v] : 
        if not visited[i]:
            result[i] = v
            DFS(i)# 재귀

# 인접 노드 저장하기
for _ in range(N-1):
    s,e  = map(int,sys.stdin.readline().split())
    nearList[s].append(e)
    nearList[e].append(s)

DFS(1)

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

BFS

import sys
from collections import deque
N = int (sys.stdin.readline())
nearList = [[] for _ in range(N+1)]# 인접 노드 저장 리스트
visited = [False]*(N+1) # 모든 노드 방문했는지 확인
result = [0]*(N+1)

# BFS
def BFS(v):
    Myqueue = deque()
    Myqueue.append(v)
    visited[v] = True
    while(Myqueue): # 마이큐에 값이 있을 때까지
        NowNode = Myqueue.popleft() #선입선출
        for i in nearList[NowNode]:
            if not visited[i]:
                visited[i] = True
                result[i] = NowNode
                Myqueue.append(i)

# 인접 노드 저장하기
for _ in range(N-1):
    s,e  = map(int,sys.stdin.readline().split())
    nearList[s].append(e)
    nearList[e].append(s)

BFS(1)

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

---

🥇 골드 5

1068번: 트리

리프 노드 = 트리에서 가장 하위에 위치한 노드 / 자식 노드가 없는 노드

 

"리프 노드를 어떻게 제거하는가?"

=> 탐색 수행 중 제거 노드 등장 시 그 아래로 탐색을 하지 않음

import sys
from collections import deque
N = int(sys.stdin.readline())
nearList = [[] for _ in range(N)]
visited = [False]*(N) 
result = 0
Mlist = list(map(int, sys.stdin.readline().split()))
delNode = int(sys.stdin.readline())

def BFS(v):
    global result
    Myqueue = deque()
    Myqueue.append(v)
    visited[v] = True
    while(Myqueue):
        NowNode = Myqueue.popleft()
        for i in nearList[NowNode]:
            if not visited[i] and i != delNode: #삭제 노드면 큐에 추가하지 않음
                visited[i] = True
                Myqueue.append(i)
        if len(nearList[NowNode]) == 1: # 리프 노드인지 확인
            result += 1

for i in range(N):
    if Mlist[i] == -1 :
        rootNode = i
    else:
        nearList[Mlist[i]].append(i)
        nearList[i].append(Mlist[i])

if delNode == rootNode:
    print(0)
else:
    BFS(rootNode)
    print(result)

틀림

그 이유는!

len(nearList[NowNode]) == 1:에서 부모 노드만 인접리스트에 있으면 리프 노드라고 생각했는데

아 삭제된 애가 자식으로 하나 달려 있었으면 삭제 후에는 리프 노드가 될 수도 있어서 이 케이스에는 2여도 되는 거였다.

import sys
from collections import deque
N = int(sys.stdin.readline())
nearList = [[] for _ in range(N)]
visited = [False]*(N) 
result = 0
Mlist = list(map(int, sys.stdin.readline().split()))
delNode = int(sys.stdin.readline())

def BFS(v):
    global result
    Myqueue = deque()
    Myqueue.append(v)
    visited[v] = True
    while(Myqueue):
        NowNode = Myqueue.popleft()
        child = 0
        for i in nearList[NowNode]:
            if not visited[i] and i != delNode: #삭제 노드면 큐에 추가하지 않음
                visited[i] = True
                child += 1
                Myqueue.append(i)
        if child == 0: # 리프 노드인지 확인
            result += 1

for i in range(N):
    if Mlist[i] == -1 :
        rootNode = i
    else:
        nearList[Mlist[i]].append(i)
        nearList[i].append(Mlist[i])

if delNode == rootNode:
    print(0)
else:
    BFS(rootNode)
    print(result)

끗