그래프를 배운 후 트리를 다시 보면 간선과 정점으로 이루어진 자료구조로 그래프의 특별한 한 종류임을 알 수 있다.
기억해두면 좋은 정의는 아래와 같다.
트리에서는 임의의 노드를 루트로 만들 수 있다. → 무방향 그래프에서 하나의 노드를 선택하고 루트로 만들어서 트리 모양을 만들 수 있음
그래프에서 사용하는 BFS와 매우 비슷하지만 BFS를 돌면서 자신의 자식노드만 큐에 넣어주면 된다. 이 말은 곧 자신과 이웃한 정점들에 대해 부모만 빼고 나머지를 전부 큐에 넣으면 됨을 의미하고 그렇기 때문에 visited 배열을 들고 갈 필요가 없이 부모가 누구인지만 저장해주면 된다.
from collections import deque
graph = [] # 그래프가 만들어져 있다고 생각했을 때
parent = [] # 노드의 부모값을 저장해둘 배열
def bfs(root:int) -> None:
queue = deque()
queue.append(root)
while queue:
cur_node = queue.popleft()
for next_node in graph[cur_node]:
if parent[cur_node] == next_node: continue
queue.append(next_node)
parent[next_node] = cur_node
자식의 depth는 부모의 depth + 1임을 이용해 depth를 구할 수도 있다.
dfs도 bfs와 마찬가지로 연결된 정점들은 1개만 부모이고 나머지는 전부 자식이라는 성질을 이용해 visited 배열을 쓰는 대신 부모 배열과 depth 배열을 채우면서 처리가 가능하다.
graph = []
parent = []
depth = []
# 스택 코드
def dfs(root:int) -> None:
stack = []
stack.append(root)
while stack:
cur_node = stack.pop()
for next_node in graph[cur_node]:
if parent[cur_node] == next_node: continue
stack.append(next_node)
parent[next_node] = cur_node
depth[next_node] = depth[cur_node] + 1
# 재귀 코드
def dfs(cur_node:int) -> None:
for next_node in graph[cur_node]:
if parent[cur_node] == next_node: continue
parent[next_node] = cur_node
depth[next_node] = depth[cur_node] +1
dfs(next_node)
#단순 순회
def dfs(cur_node:int, par:int) -> None:
for next_node in graph[cur_node]:
if par == next_node: continue
dfs(next_node, cur_node)
서로 다른 트리라고 하더라도 순회결과가 일치할 수 있다.
boj-11725
import sys
input = sys.stdin.readline
sys.setrecursionlimit(120000)
N = int(input())
parent = [0] * (N+1)
graph = [[ ] for _ in range(N+1)]
for _ in range(N-1):
node1, node2 = map(int, input().split())
graph[node1].append(node2)
graph[node2].append(node1)
def dfs(cur_node:int) -> None:
for next_node in graph[cur_node]:
if parent[cur_node] == next_node: continue
parent[next_node] = cur_node
dfs(next_node)
dfs(1)
for idx in range(2, N+1):
print(parent[idx])
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
parent = [0] * (N+1)
graph = [[ ] for _ in range(N+1)]
for _ in range(N-1):
node1, node2 = map(int, input().split())
graph[node1].append(node2)
graph[node2].append(node1)
def bfs(root:int) -> None:
queue = deque()
queue.append(root)
while queue:
cur_node = queue.popleft()
for next_node in graph[cur_node]:
if parent[cur_node] == next_node: continue
queue.append(next_node)
parent[next_node] = cur_node
bfs(1)
for idx in range(2, N+1):
print(parent[idx])
boj-1991
import sys
input = sys.stdin.readline
N = int(input().rstrip())
left = [0] * (N+1)
right = [0]* (N+1)
for _ in range(N):
parent, left_child, right_child = input().rstrip().split()
parent = ord(parent) - ord("A") +1
if left_child != ".": left_child = ord(left_child) - ord("A") +1
if right_child != ".": right_child = ord(right_child) - ord("A") +1
left[parent] = left_child
right[parent] = right_child
def pre_order(cur_node):
cur_node_to_char = chr(cur_node + ord("A") -1)
print(cur_node_to_char, end="")
if left[cur_node] != ".": pre_order(left[cur_node])
if right[cur_node] != ".": pre_order(right[cur_node])
def in_order(cur_node):
cur_node_to_char = chr(cur_node + ord("A") -1)
if left[cur_node] != ".": in_order(left[cur_node])
print(cur_node_to_char, end="")
if right[cur_node] != ".": in_order(right[cur_node])
def post_order(cur_node):
cur_node_to_char = chr(cur_node + ord("A") -1)
if left[cur_node] != ".": post_order(left[cur_node])
if right[cur_node] != ".": post_order(right[cur_node])
print(cur_node_to_char, end="")
pre_order(1)
print()
in_order(1)
print()
post_order(1)