문제 링크 http://icpc.me/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 풀이 bfs/dfs를 이용하여 풀 수 있다. 임의의 점을 하나 잡고, 그 점에서 가장 먼 점을 구한다. 그때 이 가장 먼 점을 a라고 하자. a에서 가장 먼 점을 구한다. 그때 이 점을 b라고 하자. 그럼 이때 a, b의 거리가 트리의 지름이 되고, 이 두 점이 트리에서 가장 먼 두 점이다. 그럼 이제 이 두 점 사이 거리를 제외한 가장 먼 거리를 찾아야하기 때문에, a에서 b를 제외한 가장 먼 거리를 ..

문제 링크 https://www.acmicpc.net/problem/3584 풀이 LCA(Lowest Common Ancestor) 기본 문제다. 최소 공통 조상은 트리에서 어떤 두 정점이 같은 가장 가까운 조상을 의미한다. 최소 공통 조상을 구하기 위해서 각 노드의 깊이를 저장해 놓는다. 그 후 a, b의 공통 조상을 찾는다고 한다면 a와 b의 깊이를 동일하게 맞춘 후 둘 다 한 칸씩 조상으로 이동하며 서로 같은지 확인하면 조상이 일치한 지 확인할 수 있다. 시간 복잡도는 O(depth)이다. cf) 이 문제는 단방향 그래프이므로 루트 노드를 따로 찾아줘야 한다. 코드 #include #include #include using namespace std; vector v[10004]; int par[10..

풀이 방법 이 문제는 트리 + dp를 이용하는 문제이다. dp는 dp[현재 노드 번호][현재 노드가 우수인지 아닌지 여부]로 정의한다. 2번 조건에 의해 현재 노드가 우수 마을이면 항상 다음 노드는 우수 마을이 아니고, 우수마을이 아니라면 다음 노드는 우수마을일수도 있고 아닐 수도 있다. 3번 조건은 1번 조건에 의해 자연스럽게 만족된다. 우수x -> 우수x -> 우수x 이런식으로 계속해서 될 수 있다고 착각을 하여 시간을 많이 뺏겼다. 하지만 우수x -> 우수x -> 우수x 이 상황은 항상 올 수 없다. 왜냐하면 우수x -> 우수x -> 우수x 이 상황보다 우수x -> 우수 -> 우수x 이 상황이 항상 더 크기 때문에 최댓값을 유지하기 위해서는 우수x가 계속해서 올 수 없다. 코드 #include #i..

풀이 방법 이 문제는 트리에서 dp를 이용하는 문제이다. dp[현재 노드][현재 노드가 얼리어답터인가 여부]로 dp테이블을 만들고 현재 노드가 얼리어답터가 아니라면 자식노드는 항상 얼리어답터이고, 얼리어답터라면 얼리어답터일수도, 아닐수도 있다. 이 문제는 이 문제 와 매우 비슷하여 쉽게 해결하였다. 코드 #include using namespace std; vector v, tree; int dp[1000006][2]; bool visited[1000006]; //단방향 그래프로 바꾼다 void dfs(int cur) { if (visited[cur]) return; visited[cur] = true; for (auto nxt : v[cur]) { if (!visited[nxt]) { tree[cur]..