[알고리즘풀이]백준 3584: 가장 가까운 공통 조상 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 5639번 가장 가까운 공통 조상를 풀었습니다. 이를 정리해보고자 합니다.

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

 

본문

1) 문제

2) 과정

이번 문제는 너무 빨리 풀어서 골드가 맞을까 생각했었어요. 생각부터 제출까지 40분도 안걸려서 실버겠거니 했는데 골드라 알고리즘 공부하면서 가끔씩 찾아오는 뿌듯함에 기분이 좋았습니다!

 

이번 문제에서 그나마 어려웠던 부분을 뽑자면 입력받은 값을 트리로 만드는 거였어요.

그 부분만 잘해냈다면 푸는데는 크게 어려움이 없었을 겁니다!

 

제가 이 문제를 푼 방법은 다음과 같아요.

1. 입력받은 값을 이용하여 트리로 만든다. (노드의 부모를 노드가 알고있는 방향으로 짜야할 듯)
2. 입력받은 두 정점 중 한 정점의 부모 노드들을 모두 찾는다.
3. 다른 한 정점의 부모 노드를 따라가며 두 정점이 만나는 가장 가까운 지점(깊이가 가장 큰 공통 조상)을 발견하면 탐색을 종료하고 그 값을  출력한다.

 

문제를 다 풀고는 검색이 주 업무인 한 노드의 값을 저장하는 배열을 ArrayList에서 HashSet으로 변경해 속도와 메모리를 개선해봤습니다. 이번 풀이의 버전도 HashSet으로 작성한 버전이예요!

 

2-1) main

public static void main(String[] args) throws IOException{
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // get testcase
        int T = Integer.parseInt(br.readLine());
        for(int test = 0; test<T;test++){
            // get node nums
            int N = Integer.parseInt(br.readLine());
            // initialize lines            
            int[] orgArr = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int l=1;l<N;l++){
                int p = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                orgArr[c] = p;
                st = new StringTokenizer(br.readLine());
            }
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // Logic
            // find a's ancestor
            HashSet<Integer> aAnc = new HashSet<>();
            int tmp=a;
            int end=a;
            while(end!=0){
                aAnc.add(tmp);
                end = tmp;
                tmp = orgArr[end];
            }
            // find b's ancestor & check is in aAnc(a' ancestor list)
            tmp=b;
            end=b;
            while(end!=0){
                if(aAnc.contains(tmp)) break;
                end = tmp;
                tmp = orgArr[end];
            }
            
            // Output - print common ancestor number
            System.out.println(tmp);
        }
    }

그렇게 어렵게 이해가 요구되는 부분도 없었고 간단한 주석만으로도 이해가 되는 코드라 주석도 많이 안달았어요.

코드를 요약하면 "입력을 받으며 자식이 부모를 아는 방향으로 트리를 만든다 -> a(가장 가까운 공통 조상을 구할 두 노드 중 하나)의 조상들을 모은다 -> b의 조상을 탐색하며 a의 조상중 발견된 첫 값을 출력한다"로 볼 수 있겠네요!

 

3) 전체코드

이번엔 main에 전부라 따로 전체코드는 안달아둘게요! 대신 깃헙에 가시면 바로 확인할 수 있습니다! 

소요시간, 아이디어, 에러로그 등 더 자세히 이번 문제를 보고싶으시다면, 아래 깃헙 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/tree/BOJ3584.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비