백준

17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net ✅ 문제 설명 1번 정점(루트)에 W만큼의 물이 고여있고, 다른 정점들에는 물이 고여있지 않은 상태입니다. 이때 모든 정점은 아래의 작업을 매초 마다 반복합니다. 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면 동일한 확률로 그 중 하나를 고른다. 만약 부모 정점이 자신에게 물을 흘려보냈다면 받아서 쌓아 둔다. 위 작업이 다 끝나서 더 이상 물이 움직이지 않을 때..

2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net ✅ 문제 설명 BOJ_4256 문제와 비슷한 문제입니다. (https://wnszero.tistory.com/10) 이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더를(전위순회) 구하는 문제입니다. ✅ 접근 방식 중위순회, 후위순회 2개의 결과를 종합하여 각각의 결과에서의 루트와 왼쪽서브트리, 오른쪽 서브트리를 알아내고, 이를 이용해서 (루트)(왼쪽 서브트리)(오른쪽 서브트리)순으로 탐방순서를 배치해 전위순회를 시행하면 원하는 결과를 얻을 수 있습니다. ✅ 코..

4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net ✅ 문제 설명 이진 트리의 전위순회, 중위순회 결과가 주어졌을 때, 후위 순회의 결과를 유추하는 문제입니다. 이때, 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어집니다. ✅ 접근 방식 저번 포스팅이었던 이진 검색 트리에서 썼던 로직과 같은 로직을 이용했습니다. (참고) [BOJ_5639] 이진 검색 트리 (python) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작..

1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net ✅ 문제 설명 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 트리의 지름이라고 정의할 때, 트리의 지름을 구하는 문제입니다. ✅ 접근 방식 트리의 지름을 구하는 방법은 다음과 같습니다. 1) 시작노드(=아무노드나 가능)에서 가장 먼 노드 A를 구합니다. 2) 노드 A를 기준으로 가장 먼 노드B를 구하면 그 두 노드(A,B) 사이의 거리가 트리의 지름이 됩니다. 이게 왜 가능할까요? 어떤 노드에서 가장 먼 노드를 구하면(1번) 그 노..