백준 3584: 가장 가까운 공통 조상 (java)

이 문제는 처음에 Union-Find랑 비슷해보여서 그래프로 접근했다가 망한 케이스다.

 

이후에는 여러 풀이 방법을 생각해봤는데 너무 복잡해져서

간단하게 구현할 수 있는 방법이 무엇일까 검색하다가

빵똥님의 풀이법을 참고하게 됐다.

 

https://dhbang.tistory.com/34

 

그리고 찾아보니까 코테에서는 함수형 프로그래밍은 굳이 안해도 되는 것 같다.

setParent()와 같은 함수는 그냥 바로 Main에 작성해도 될 것 같다.

---

 

알고리즘

트리: LCA

 

체감 난이도

★ ★ ★ ★ ☆

 

다시 풀 수 있는가?

NO

 

---

 

1. isVisited 체크

 

isVisited로 방문한 노드를 체크하고,

다른 노드의 조상을 찾을 때 체크한 노드를 마주하면 break 한다.

 

    public void findCommonAncestor(int a, int b) {
        while (a > 0) {
            isVisited[a] = true;
            a = tree[a];
        }

        while (b > 0) {
            if (isVisited[b]) {
                System.out.println(b);
                break;
            }
            b = tree[b];
        }
    }

 

전체 코드 ▼

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ3584 {
    int[] tree;
    boolean[] isVisited;

    public void setParent(int A, int B) {
        tree[B] = A;
    }
    public void findCommonAncestor(int a, int b) {
        while (a > 0) {
            isVisited[a] = true;
            a = tree[a];
        }

        while (b > 0) {
            if (isVisited[b]) {
                System.out.println(b);
                break;
            }
            b = tree[b];
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            tree = new int[N+1];
            isVisited = new boolean[N+1];

            for (int j = 0; j < N-1; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());

                setParent(A, B);
            }

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            findCommonAncestor(a, b);
        }
    }

    public static void main(String[] args) throws Exception {
        new BOJ3584().solution();
    }
}