본문 바로가기

트리

BOJ)13016 내 왼손에는 흑염룡이 잠들어 있다 문제: icpc.me/13016 오랜만에 문제 포스팅을 한다. 문제를 요약하면 한 정점 v에서 다른 정점으로의 최단거리를 dist[i] (i: 1~n) 이라고 했을 때, dist[i]의 최댓값을 모든 정점 v에 대해 구하는 문제이다. 물론 한 정점에서 dist[i]의 최댓값을 구하는건 dfs를 수행하여 쉽게 해결할 수 있지만 모든 정점에 대해 구하게 될 경우 정점의 개수가 5만이므로 시간초과를 보게 될 것이다. 하지만 조금 생각해보면 한 정점에서의 부터 다른 정점으로 부터의 최단 거리 중 최댓값은 트리의 지름의 양 끝 단말 노드 중 하나로의 거리라는 것을 알 수 있다.(만약 트리 지름의 단말 노드가 아닌 다른 리프로 부터의 거리가 최댓값이라면, 트리의 지름보다 긴 거리가 생긴다는 뜻이므로 모순이된다.) .. 더보기
BOJ)2337 트리 자르기 문제: icpc.me/2337 트리에서 임의의 몇개의 간선을 잘라서 크기가 m인 트리를 얻고 싶을 때 잘라야하는 간선의 최소 개수를 구하는 문제이다. 트리디피로 풀 수 있는 문제이다. 기존에는 트리 디피를 n^3의 방법으로 풀어왔지만 이번에 smu형님의 도움으로 n^2 log n으로 푸는 방법을 알게 되었다. 우선 dp테이블을 dp[here][k]를 here번 정점이 루트인 크기가 k인 트리를 만드는데 필요한 간선컷의 최솟값으로 정의하면 dp[here][k]를 어떤식으로 빌드할거냐면 here가 가지는 자식들은 여러개의 서브트리를 이룰것이다. 이 서브트리를 하나씩 병합하면서 dp[here][k]를 채울 것이다. 당연히 처음에는 dp[here][1]밖에 없을 것이다 .여기서 1은 곧 자기 자신이다 이는 0으.. 더보기
BOJ)14675 단절점과 단절선 문제:icpc.me/14675 트리에서 단절선인지 단절점인지 여부를 판단하는 쿼리를 처리하는 문제이다. 단절선 단절점을 직접 구해줄 필요 없이, 트리이기 때문에 모든 선은 단절선이 된다. 트리에서 단절점 여부는 리프를 제외한 모든 노드는 단절점이 된다. 트리에서 리프판단 여부는 indegree의 개수를 세주면 된다. 1234567891011121314151617181920#include #include using namespace std;int n, m, x, y, c[100010];int main() { scanf("%d", &n); for (int i = 0; i 더보기
트리에서 A와 B의 경로 사이에 C존재 여부 트리에서 임의의 노드 A,B가 있을 때 A와 B의 경로에 C가 존재하는지 여부는 어떻게 알 수 있을까? A와 B의 LCA를 LCA(A,B)라고 칭해보자. 만약 A와 B의 경로사이에 C가 존재한다면 C는 A와 LCA(A,B) 사이의 경로에 존재하거나 B와 LCA(A,B) 사이의 경로에 존재할 것이다. 일단 A와 LCA(A,B) 사이의 경로에 C가 존재한다고 가정해보자 그렇다면 LCA(A,C)==C && LCA(A,B)==LCA(C,B) 가 성립할 것 이다. 그러면 이번에는 B와 LCA(A,B)사이의 경로에 C가 존재한다고 가정해보자. 그렇다면 LCA(B,C)==C && LCA(A,B)==LCA(C,A) 가 성립할 것이다. 따라서 { LCA(A,C)==C && LCA(A,B)==LCA(C,B) }|| { L.. 더보기
BOJ)5038 Flight Planning 문제: icpc.me/5038 트리가 주어질 때 하나의 간선을 삭제하고 다시 하나의 간선은 연결하여 만든 트리의 지름이 최소가 되도록 하는 문제이다. N제한이 2500밖에 안되기 때문에 모든 간선을 다 삭제해 본 뒤 지름을 비교해보는걸 생각해볼 수 있다. 그렇다면 하나의 간선을 제거하였을 때 트리의 지름이 최소가 되도록 간선을 이어붙이려면 어떻게 붙여야할까? 바로 트리의 반지름을 이용하면 된다. 트리의 간선을 하나를 제거하면 두개의 트리가 생기게 된다. 이 때 두 트리의 반지름을 각각 구해준 뒤 반지름을 형성하는 정점들 사이에 간선을 연결하면 트리의 지름은 max(트리1의 지름,트리2의 지름,트리1의 반지름+트리2의 반지름+1)이 된다. 따라서 모든 경우에 대하여 트리의 지름을 구해준 뒤 비교하여 답을 .. 더보기
BOJ)8872 빌라봉 문제: icpc.me/8872 문제의 내용을 풀어서 설명하면 결국 포레스트가 주어졌을 때 해당 포레스트에 몇개의 간선을 추가하여 만들어진 트리의 지름의 최솟값을 구하는 문제이다. 문제의 답은 세 경우중 하나가 될 수 있는데 1.기존의 포레스트내의 트리에서의 지름중 최댓값 2-3. 포레스트 내부의 서브트리들의 반지름 중 가장큰 반지름을 가지는 서브트리에 나머지 반지름들을 길이 L로 연결하였을 때2.가장 긴 반지름 + 두번째로 긴 반지름 +L3.두번째로 긴 반지름 + 세번째로 긴 반지름 +L+L 이 세값 중 최댓값이 답이된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555.. 더보기
BOJ)10838 트리 문제: icpc.me/10838 트리에서 세가지 쿼리를 처리하는 문제이다. 1번 쿼리나 3번 쿼리에서 물어보는 질의를 답하기 위해서는 a와 b의 lca를 필수적으로 구해야한다. 고정된 트리에서 LCA는 전처리를 거친후에 logN의 시간에 구할 수 있지만 2번 쿼리가 트리의 구조를 바꿔버리기 때문에 힘들어질 뿐더러 1번, 3번 쿼리를 처리하기 위해 LCA를 구했다고 하더라도 색칠을하거나 색의 개수를 세려면 log시간에 처리하긴 힘들어보인다. 하지만 문제를 잘 읽어보면 paint와 count 연산 시 a번 노드와 b번 노드 사이의 최단경로의 길이는 항상 1,000 이하이다. 라는 조건을 찾을 수 있다. 이를 이용하여 LCA나 쿼리를 O(1000)의 시간에 해결해주면 문제를 해결할 수 있다. 123456789.. 더보기
BOJ)2820 자동차 공장 문제: icpc.me/2820 문제를 잘 읽어보면 1번을 루트로 가지는 트리 구조를 이룬다는걸 알 수 있다. 그럼 상사 X의 부하들은 어떻게 구분할 수 있을까? 트리 구조이기 때문에 X에서 Y로 가는 경로는 오직 하나일 것이다. 이걸 이용하여 X지점에서 시작한 DFS가 끝날 때 까지 탐색되는 모든 노드들은 X의 부하라는걸 알 수 있다. 이를 이용하여 1번 노드에서부터 DFS를 돌려 정점의 번호를 새롭게 매겨준 후 DFS가 끝나는 지점(마지막 부하)의 번호까지 알게 된다면 직원에 대한 증가연산을 구간에 대한 증가 연산으로 치환시킬 수 있다, 구간에 대한 증가 연산으로 치환을 했으니 레이지 프로퍼게이션을 이용한 세그먼트 트리나 ,펜윅 트리 등을 이용하여 쿼리를 처리해주면 된다. 1234567891011121.. 더보기
BOJ)9934 완전 이진 트리 문제: icpc.me/9934 완전 이진 트리가 주어질 때 이진 트리의 깊이 순서대로 출력해주면 되는 문제이다. 12345678910111213141516#include #include #include using namespace std;int k, r[1 더보기
BOJ)2275 트리의 높이 줄이기 문제: icpc.me/2275 트리에서 모든 리프까지의 거리가 H이하로 되게 만들 때 비용의 최솟값을 구하는 문제이다. 우리는 가능하다면 부모에서 높이를 줄여야지 한번에 여러 리프들의 높이를 동시에 줄이는게 가능하다는 사실을 이용하여 모든 리프에 줄여야할 가중치를 할당하고 바텀업 방식으로 부모에서 높이를 줄이는게 가능하다면 줄이는 방식으로 문제를 해결해주면 된다. 문제를 해결하기 위하여 dfs로 전처리를 해줘야하는데 해당 노드의 깊이 중첩 가중치를 미리 구해주면 쉽게 계산해 줄 수 있다. 아래 코드에서 각 배열이 의미하는건 r[v]는 v노드에서 줄여야하는 가중치이고 d[v]는 v까지의 누적 가중치이다. 123456789101112131415161718192021222324252627282930313233.. 더보기

티스토리툴바