트리

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 �� www.acmicpc.net 이 문제도 1967번과 똑같은 문제다. 다만 입력받는 방식이 조금 귀찮아졌다. 마찬가지로 1번 노드에서 DFS를 돌리고 최댓값의 인덱스를 저장해 두었다가 다시 DFS를 돌리면 된다. #include #include #include using namespace std; bool vis[100001]; vector ar[100001]; int ans, idx; void dfs(int cur, int..

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 �� www.acmicpc.net 무방향 그래프가 가중치를 포함하여 주어진 트리에서 트리의 지름을 구하는 문제이다. 지름은 가중치가 가장 긴 값이 지름이 된다. 문제는 이해가 되는데 트리의 지름에 대한 개념이 없어서 어떻게 풀어야 할지 감이 안 잡혀 다른 분들의 코드를 참고했다. 정해는 부모 노드에서 DFS를 돌려서 가장 큰 값이 나온 그 노드를 저장하고, 그 노드에서 다시 DFS를 돌려서 가장 큰 값이 나온다면 그 값이 지..

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 그래프에 입력받고 DFS이던 BFS이던 해준 뒤에 2부터 N까지의 부모 노드를 저장해주면 된다. #include #include #include using namespace std; vector ar; bool vis[100001]; map M; void dfs(int cur) { vis[cur] = true; for (auto i : ar[cur]) { if (!vis[i]) { M[i] = cur; dfs(i); } } } int main() { ios::sync_wit..

www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 기초적인 트리 순회 문제. 처음에는 노드로 트리를 구현하여 순회시키려 했지만 생각보다 난이도가 있어서 배열로 구현했다. 이런 식으로 서브 노드가 더 이상 존재하지 않으면 '.'을 넣어 끝임을 표시한다. for (int i = 0; i > a >> b >> c; tree[a - 'A'][0] = b; tree[a - 'A'][1] = c; } [0]은 왼쪽, [1]은 오른쪽으로..