트리11 FORTRESS - 요새 (트리) https://algospot.com/judge/problem/read/FORTRESS 트리의 지름을 구하는 문제. 임의의 한 점에서 가장 먼 점u, u에서 가장 먼 점v에 대해 u~v거리구하면된다. 서로가 서로에게 포함되거나 포함하는 원들이 최대 100개 주어진다.(겹치거나 접하는 경우 없음) 이때 임의의 두 점 사이에 건너야 하는 벽의 최대 개수를 구해라. 큰 원u가 작은원 v를 포함하는 것을 u->v라 할때 전체 형태는 트리의 형태가 된다. 간선을 이어줄때, 예를들어 a->b->c 인 경우 a->c를 잇지 않도록 주의한다. 반지름을 기준으로 오름차순 정렬하여 적절히 처리해주면 된다. 그리고 트리의 지름을 구하면 된다. 간선을 이어주는 부분 for (int i = 0,x,y,r; i < n; i++).. 2020. 2. 8. 트리 struct treeNode { int element; treeNode * parent; vector children; } * 이진 트리: 자식을 최대 두 개 갖는 트리 * 이진 탐색 트리: 이진트리. 어떤 노드에서 left엔 자기보다 작은 값, right엔 자기보다 큰 값을 유지하는 식 * 힙: 포화 이진트리. 노드가 들어갈 수 있는 자리가 비어있는 경우가 없으므로 일반적으로 배열로 구현. * 구간트리: * 상호 배타적 집합 구조(disjoint set) : 각 노드는 부모를 가리키는 포인터는 있지만 자식에 대한 정보는 없다. 2020. 2. 8. 그래프 크기 구하기 int sz[MAX]; //따로 초기화 해둘 필요 없음 bool vst[MAX]; void dfs(int curr) { vst[curr] = true; sz[curr] = 1; for (int next : adj[curr]) { if (!vst[next]) { dfs(next); //빠져나오면 curr의 next방향 서브트리의 sz모두 초기화 sz[curr] += sz[next]; } } } * 메인함수에서 dfs(rootNode)로 수행해야 모든 정점에 대해 구할 수 있음 * 양방향/단방향(부모->자식) 간선을 사용한 트리 모두에 대해 사용 가능 bool vst[MAX]; int dfs(int curr){ vst[curr]=true; int ccnt=1; for(int next: adj[curr]){ .. 2020. 1. 7. 이전 1 2 3 다음