[백준 3584] 가장 가까운 공통 조상 (JAVA)

백준 3584번 문제 - 가장 가까운 공통 조상

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

---

문제 분석

 

 

• 루트가 있는 트리가 주어졌을 때, 가장 가까운 공통 조상을 출력해라

---

해결 키 포인트

• 문제를 보고 depth를 통일시키고 부모를 확인할 때, 부모가 동일하면 출력하면 되겠구나 쉽게 생각했다.
• 고민은 "depth를 어떻게 확인하냐" 뿐
  • 입력을 받고 맵에 해당 값이 존재하면 해당 depth +1, 존재하지 않으면 0으로 (최상위부모)로 설정하고 자식 노드에게는 부모 번호만 알려줬다
    → 이 방법의 문제: 최상위 부모부터 순서대로 입력받는다는 보장이 없었다
  • 자식 노드에 부모 번호만 알려주지 말고, 부모노드 그 자체를 알려주고, 나중에 depth를 알아낼때 부모노드 depth +1 로 알아내가 설정
    → 맵에 존재여부 확인을 부모뿐만 아니라 자식도 확인하게 코딩

---

코드

 

1. 테스트 케이스 입력받고 테스트 케이스 만큼 반복
2. 노드 개수 입력
3. 노드가 입력되었는지 체크하기 위한 맵 제작
4. 트리 간선 입력 (부모 자식 관계 입력)
     - 부모 노드가 입력받았던 적 있는 경우, 노드 가져오기
        없는 경우, 최상위 노드 취급하여 생성
     - 자식 노드가 입력받았던 적 있는 경우, 노드 가져와서 부모 노드만 새로 등록
        없는 경우, 부모노드의 자식으로 생성
5. 가까운 부모노드를 알고싶은 비교 군 입력
6. 비교군 두 노드의 트리 깊이가 같을 때까지 비교해서 맞추기
7. 두 노드의 깊이가 같아졌으므로, 부모가 같을 때까지 둘 다 부모 노드로 이동
8. 부모 노드가 같아졌으므로 부모노드 출력

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 테스트 케이스 입력
        int T = Integer.parseInt(br.readLine());

        // 테스트 실행
        for (int t = 0; t < T; t++) {
            // 노드 개수 입력
            int N = Integer.parseInt(br.readLine());

            // 노드가 입력됬는지 체크하기 위한 맵
            HashMap<Integer, Node> trees = new HashMap<>();

            // 트리 간선 입력 (부모 자식 관계 입력)
            for (int i = 0; i < N - 1; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());

                // 부모 노드가 입력받았던 적 있는 경우, 노드 가져오기
                // 없는 경우, 최상위 노드 취급하여 생성
                Node a;
                if (trees.containsKey(A)) {
                     a = trees.get(A);
                } else {
                    a = new Node(null, A);
                    trees.put(A, a);
                }

                // 자식 노드가 입력받았던 적 있는 경우, 노드 가져와서 부모 노드만 새로 등록
                // 없는 경우, 부모노드의 자식으로 생성
                if(trees.containsKey(B)) {
                    Node b = trees.get(B);
                    b.parent = a;
                }
                else {
                    trees.put(B, new Node(a, B));
                }
            }

            // 비교 군 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            Node first = trees.get(Integer.parseInt(st.nextToken()));
            Node second = trees.get(Integer.parseInt(st.nextToken()));

            // 두 노드의 트리 깊이가 같을 때까지 비교
            while(first.getDepth() != second.getDepth()) {
                if(first.getDepth() > second.getDepth())
                    first = first.parent;
                else
                    second = second.parent;
            }

            // 두 노드의 깊이가 같아졌으므로, 부모가 같을 때까지 둘 다 부모 노드로 이동
            while(first.current != second.current) {
                first = first.parent;
                second = second.parent;
            }

            // 부모 노드가 같아졌으므로 부모노드 출력
            bw.write(first.current + "\n");
        }
        bw.flush();
        bw.close();
    }
    public static class Node {
        int current;
        Node parent;

        public Node(Node parent, int current) {
            this.parent = parent;
            this.current = current;
        }

        // 깊이를 알아내는 함수
        public int getDepth() {
            if(parent != null) {
                return parent.getDepth()+1;
            }
            else return 0;
        }
    }
}