트리6 [백준] 2250번 - 트리의 높이와 너비 (C++) 문제 및 풀이 문제) 백준 - 트리 - 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 중위 선회를 통해 해방 레벨에서의 최소 idx와 최대 idx를 memo 합니다. 그 후, 1부터 N까지 너비의 최댓값을 찾아 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/2250_%ED%8A%B8%EB%A6%A.. 2022. 3. 18. [백준] 20294번 - 트리의 기둥과 가지 (C++) 문제 및 풀이 문제) 백준 - DFS/트리 - 트리의 기둥과 가지 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net DFS를 통해서 기둥과 가지를 탐색합니다. 기둥의 기준은 이어진 노드가 단 하나여야 되므로 graph의 사이즈가 1인 노드가 이어질 때까지 탐색합니다. 기둥의 마지막 부분을 저장해 가장 긴 가지를 탐색해 출력합니다. C++ 소스코드).. 2022. 2. 22. [백준] 4803번 - 트리 (C++) 문제 및 풀이 문제) 백준 - DFS - 트리 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1번 노드부터 탐색하면서 트리의 개수를 계산합니다. 그래프에서 노드의 개수와 간선의 개수를 계산하여 cntEdge(i) / 2 == cntNode(i) - 1을 통해 트리 여부를 판별합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/480.. 2022. 2. 12. [백준] 9934번 - 완전 이진 트리 (C++) 문제 및 풀이 문제) 백준 - 트리(Tree) - 완전 이진 트리 -> https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위 순회(In-Order)가 주어졌을 때, 트리의 개형을 복원하는 문제. 트리의 Root -> Sub Left Tree -> Sub Right Tree 순으로 재귀적으로 탐색하면 해결 C++ 소스코드) 2021. 7. 14. [백준] 11725번 - 트리의 부모 (파이썬) 문제) 백준 - 트리 (Tree) - 트리의 부모 -> www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리 상에서 연결된 두 정점을 인접 리스트 방식으로 나타낸다. 문제에서 트리의 루트가 1번으로 주어졌으므로 dfs를 이용해 1번부터 시작해 노드에 연결된 노드들을 순회한다. parent 리스트에 부모를 채킹(Checking)하면서, 0일 겨우 방문하지 않은 노드로 인식해 부모 노드로 저장한다. 소스 코드) import sys sys.setrecursionlimit(10 ** 8) n = int(input()) tree .. 2021. 3. 12. [백준] 1068번 - 트리 (파이썬) 문제) 백준 - 그래프 이론/트리 - 트리 -> www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 인접 행렬 방식으로 graph를 False로 초기화한다. 2. 입력으로 들어온 부모 노드들의 정보를 이용해 graph의 연결을 채워주고 root를 선정한다. 3. 세 번째 줄 입력에 나오는 지울 노드의 모든 연결을 끊어준다.(False로 설정) 4. dfs로 root부터 탐색해 리프 노드 개수를 구해준다. 반성) 트리 문제라 생각해서 인접 행렬의 활용과.. 2021. 2. 20. 이전 1 다음 반응형
