문제http://boj.ma/31476 31476번: :blob_twintail_thinking: boj.ma 풀이문제 요약완전 이진 트리에 대해 주어진 규칙대로 bfs/dfs했을 때, 최소 비용을 구하자.아이디어문제에서 주어진 규칙은 다음과 같다.양갈래 블롭의 탐색: 기본 탐색 비용 U로 bfs를 했을 때, 두 자식이 존재할 때 마다 T만큼 비용이 증가한다.포니테일 블롭의 탐색: 기본 탐색 비용 U로 dfs를 했을 때, 더 이상 탐색할 자식 노드가 없어 돌아올 때도 U만큼 비용을 지불한다. 단, 탐색 가능한 마지막 노드에 도달한 후에는 복귀 비용을 지불하지 않는다.포니테일 블롭의 탐색의 구현을 하기 위해서는 방문 가능한 노드의 수를 알고 있어야 한다. 따라서 양갈래 블롭 탐색을 먼저 해주며 방문 가능한..

문제https://www.codetree.ai/trails/complete/curated-cards/intro-parent-node-of-the-tree/introductionCode Tree | Learning to Code with Confidence풀이각 노드의 부모 노드를 구하는 문제다.주어진 트리 정보에 대해 dfs를 하며 각 부모 노드를 구하면 된다. private static void dfs(int node) { for (int child : tree.get(node)) { if (parent[child] == -1) { parent[child] = node; dfs(child); ..

문제https://www.acmicpc.net/problem/11438풀이기존에 선형 탐색으로 O(N)만에 LCA를 구하는 방법으로는 이 문제를 해결할 수 없다.2025.01.15 - [PS/Baekjoon Online Judge] - [백준 11437] LCA [Java] [백준 11437] LCA [Java]문제https://www.acmicpc.net/problem/11437풀이DFS를 통해 모든 노드의 부모 노드와, 깊이를 구한 후 LCA를 구하는 기본 문제입니다.이를 위해서 양방향 그래프를 구성해야 합니다.문제에서 트리의 루트는 1kyr-db.tistory.com각 쿼리에 대해 O(logN)안에 LCA를 찾을 수 있는 방법에 대해 알아보자.깊이가 다른 두 노드의 깊이를 맞추고 LCA를 탐색하는 ..

문제https://www.acmicpc.net/problem/3584풀이문제에서 주어지는 간선이 부모-자식 관계를 나타내고 있기 때문에 별도의 알고리즘 없이 dfs으로 선형탐색하면 된다. 우선 정점 u에 대해 루트 노드까지 탐색하며 방문 표시를 해주자.정점 v에 대해 루트 노드까지 방문하지 않은 노드까지 탐색하면 된다.소스코드보기

문제https://www.acmicpc.net/problem/2533풀이우선, 주어지는 루트가 없으며, 어디서 탐색해도 상관없다.그래프를 구성 후 dfs를 진행하자. 얼리 어답터의 수가 최소가 되도록 만드는 방법에 대해 알아보자.맨 처음 리프노드는 자기 자신이 얼리 어답터라고 가정해야 한다.하지만, 부모 노드가 존재한다면 리프 노드는 얼리 어답터가 아닌 상태가 정답이다.여기서 dp는 두 상태(EARAY, GENERAL)에 대해 고려해야 한다.dp[i][j] : 상태가 i일때 j ~ N에 필요한 최소 얼리 어답터의 수dfs를 통해 방문을 진행하면 방문 표시와 함께 현재 정점이 얼리 어답터인 경우를 세주자.리프 노드까지 도달 후 리프 노드들이 얼리 어답터라고 표시된 후 부모 노드로 돌아와서 부모 노드의 두 ..

문제https://www.acmicpc.net/problem/3584풀이주어지는 트리에 대해 두 정점의 공통 조상을 찾는 문제다.이미 부모-자식에 대한 정보가 주어지므로, 입력과 동시에 parent를 바로 구성할 수 있다. 공통 조상을 구해야하는 두 정점 중 한 정점으로부터 루트노드까지 방문해주고,다른 정점도 동일하게 방문하지 않은 부모 노드를 따라 방문하면 된다.이미 방문한 적 있는 부모노드는 공통 조상 노드이므로 탐색을 중단하고 반환해주면 된다.소스코드보기