백준/트리
-
11437 LCA백준/트리 2022. 5. 8. 22:38
1. 풀이 다른 사람 블로그를 참고했다. 일단 그림으로 설명하겠다. 문제 예제에 6번 노드와 11번 노드의 부모를 찾으라고 되어있다. 이때, 6번 노드와 11번 노드의 level 이 다르다. 트리에서 level 이란, 루트 노드로부터 깊이를 의미하는데, 루트 노드의 level = 1이다. 이때 level 이 더 큰 11번 노드와 관련해서 변화를 준다. => 11번 노드의 부모 노드를 타고 이동하면서 노드 6과 level 이 같아지는 노드 번호를 찾는다. 5번 노드와 6번 노드의 level 이 같다. 이때부터는 5번, 6번 노드의 각 부모 노드를 타고 올라가면서 그 값이 같아지는 경우를 찾으면 된다. 5번 노드의 부모 노드와, 6번 노드의 부모 노드가 2로 같다. 정답은 2가 된다. 위에서는 쉽게 풀렸지만..
-
11725 트리의 부모 찾기 (자바)백준/트리 2022. 2. 19. 16:15
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static boolean check []; static int parents []; static ArrayList list; public static void main(String args[]) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.par..