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

solved.ac = 골드 4

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

3584번: 가장 가까운 공통 조상

 

1. 접근

 

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

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

 

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

 

 

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

 

 

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

 

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

 

 

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. 전체 코드