BOJ 3584번 가장 가까운 공통 조상 자바(java) 풀이 랭크 : 골드4 백준 온라인 저지(BOJ) 3584번 가장 가까운 공통 조상 문제 자바 풀이 백준 3584번 가장 가까운 공통 조상 문제정리 테스트 케이스와 트리를 구성하는 노드의 수 N이 주어진다. 트리를 구성하는 간선 정보가 주어질 때, A B가 주어지면 A가 B의 부모라는 뜻이다. 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어진다. 이때 두 노드의 가장 가까운 공통 조상을 출력한다. 문제풀이 이 문제는 LCA(Lowest Common Ancestor)문제 입니다. LCA를 검색하면 정리된 많은 자료들을 볼 수 있습니다. 만약 트리의 루트가 어떠한 노드로 고정되어 있다면 dfs를 통해 탐색할 수 있습니다. 하지만 이 문제는 루..

BOJ 11437번 LCA 자바(java) 풀이 랭크 : 골드3 백준 온라인 저지(BOJ) 11437번 LCA 문제 자바 풀이 백준 11437번 LCA 문제정리 1~N번으로 번호가 매겨진 정점들이 주어진다. 루트는 1번이다. 가장 가까운 공통 조상을 알고 싶은 m개의 쌍이 주어진다. n-1개의 트리 상에서 두 정점의 연결 정보가 주어진다. 이때 A B라고 주어질때 A가 부모라는 보장이 없다. 문제풀이 이 문제는 LCA(Lowest Common Ancestor)문제 입니다. LCA를 검색하면 정리된 많은 자료들을 볼 수 있습니다. 이 문제는 depth를 모두 구하고 부모와 자식간의 관계를 구하여 트리를 만든 다음에 구하고자 하는 정점의 depth를 맞춰준다음 같은 노드가 될 때 까지 부모를 타고 하나씩 올..