시나위

https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 트리 문제이다. 트리를 만들고 순회하면 된다. 특정 노드의 부모가 가진 색깔과 노드가 원하는 색깔이 다른 경우 1 을 더한값을 계속 올려주면 된다. import sys; input = sys.stdin.readline sys.setrecursionlimit(10**9) def order(cur_node, cur_color, parent, adj_list, color): ret = 0 if..

https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 트리 문제이다. 입력으로 주어지는 값은 양방향 그래프이고 인접리스트를 사용해서 노드끼리 연결 시킨다. 그리고 트리를 순회할때 parent 노드와 다른 번호의 노드만 순회를 하면 leaf 노드를 찾을수 있다. leaf node를 찾으면 1을 리턴해주고 이 값들을 모두 더해주면 leaf 노드의 개수를 찾을수 있다. import sys; input = sys.s..

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 특정 노드를 정점으로 하는 서브 트리의 정점의 개수를 구해야한다. 무방향 그래프를 받아서 연결시켜주고, 루트 노드에서 시작해서 후위 순회로 자식 노드의 개수를 더해주면 된다. 이때 visit 로 방문했는지도 체크하고 해당 노드에서 자식 노드의 개수를 저장한다. 순회가 끝나면 visit에 자식 노드의 개수가 저장되어있으므로 특정 노드를 ..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net import sys; input = sys.stdin.readline N = int(input()) node_parent = [-1 for _ in range(N)] node_son = [[] for _ in range(N)] root = 0 for son, parent in enumerate(map(int, input().split())): if parent == -1: root = son..

www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net import sys; input = sys.stdin.readline n = int(input()) inorder = list(map(int, input().split())) postorder = list(map(int, input().split())) preorder = [] def order(inorder, postorder): if postorder == inorder: return reversed(postorder) ret = [post..