백준 3584 가장 가까운 공통 조상 Java

백준 3584 가장 가까운 공통 조상 Java

728x90

solved.ac = 골드 4

https://www.acmicpc.net/problem/3584

1. 접근

최초 접근 방법을 생각해내기까지 시간이 오래 걸렸지만 알아낸 이후부터는 비교적 쉽게 풀어낸 문제다!

저번 오리 문제와 마찬가지로 루트에서부터 내려가는 것이 아닌 공통 조상을 찾아야 하는 두 노드로부터 시작해보자!

예제 속 두 개의 케이스 중 첫 번째 케이스를 그림으로 보면 다음과 같다.

이 때, 순서에 상관은 없지만 7이 먼저 루트를 향해 체크하면서 이동한다고 가정하면 이동 경로는 다음과 같을 것이다.

7이 루트 노드인 8에 체크하며 도착했으니 두 번째 노드인 16도 체크하며 이동하다 보면 4에서 앞 노드가 이미 체크한 것을 확인할 수 있다.

위 그림들과 같이 각 노드의 부모를 타면서 루트를 이동해야 하니 최초 입력 시 각 노드의 부모를 받아주고 한 개의 노드 먼저 루트로 이동시키고 두 번째 노드도 루트로 이동하는 도중 처음으로 만난 체크되어 있는 노드가 최소 공통 조상 노드가 된다.

728x90

2. 풀이

변수 세팅

static int T, N; static int[] parent; static boolean[] visit; public static void main(String[] args) throws IOException { T = Integer.parseInt(br.readLine()); // 테스트 개수 while (T --> 0) { N = Integer.parseInt(br.readLine()); // 노드의 개수 parent = new int[N + 1]; visit = new boolean[N + 1]; for (int i = 1; i < N; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()); parent[y] = x; // y의 부모는 x다. } // 가장 가까운 조상을 찾아야 하는 노드 두 개 st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()); solution(x, y); } }

각 노드 루트로 이동 및 체크

static void solution(int x, int y) { // x 노드를 루트 노드까지 이동시킨다. while(x > 0) { visit[x] = true; x = parent[x]; } // y 노드를 루트 노드로 이동시키는 과정에서 처음 만난 노드는 최소 공통 조상 while (y > 0) { if (visit[y]) { System.out.println(y); break; } y = parent[y]; } }

3. 전체 코드

728x90

from http://dhbang.tistory.com/34 by ccl(A) rewrite - 2021-12-17 16:27:00