[BOJ] 백준 3584. 가장 가까운 공통 조상

2024. 4. 7. 15:26· Java/BOJ

문제

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

 

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

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두

www.acmicpc.net


풀이

 가장 가까운 공통 조상을 찾는 문제입니다. LCA의 풀이법인, 세그먼트 트리나, Sparse table을 사용하지 않고,  parents, check 배열을 통해 해결했습니다. 

 

 우선 입력이 부모와 자식이 구분되기 때문에, 입력을 받으며 해당 정점의 부모를 parents 배열에 입력합니다. 

 

 그리고 공통 조상을 구할 노드 중 하나를 parents 배열을 통해 타고 올라가면서, 방문 시 check 배열을 true로 바꾸어줍니다.

 

 나머지 하나의 노드를 다시 parents 배열을 타고 올라가면서 check 배열을 확인하는데, 만약 check 배열이 true라면 해당 정점이 가장 가까운 공통 조상입니다.


소스코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N;
    static int A, B;
    static int ans;
    static int[] parents;
    static boolean[] checked;

    public static void main(String[] args) {
        int T = sc.nextInt();
        for(int tc=0;tc<T;tc++){
           input();
           findLCA();
           System.out.println(ans);
        }
    }

    static void input(){
        N = sc.nextInt();
        parents = new int[N+1];
        checked = new boolean[N+1];
        for(int i =0; i<N-1;i++){
            int st = sc.nextInt();
            int ed = sc.nextInt();
            parents[ed] = st;
        }
        A = sc.nextInt();
        B = sc.nextInt();
    }

    static void findLCA(){
        int temp = A;
        while(temp != 0){
            checked[temp] = true;
            temp = parents[temp];
        }
        int temp2 = B;
        while(temp2 != 0){
            if(checked[temp2]) {
                ans = temp2;
                return;
            }
            temp2 = parents[temp2];
        }
    }
}

'Java > BOJ' 카테고리의 다른 글

[BOJ] 백준 1202. 보석도둑  (0) 2024.04.10
[BOJ] 백준 11437. LCA  (0) 2024.04.08
[BOJ] 백준 17281. 야구  (0) 2024.04.02
[BOJ] 백준 24042. 횡단보도  (0) 2024.03.30
[BOJ] 백준 2531. 회전초밥 (+15961. 회전초밥)  (0) 2024.03.28
'Java/BOJ' 카테고리의 다른 글
  • [BOJ] 백준 1202. 보석도둑
  • [BOJ] 백준 11437. LCA
  • [BOJ] 백준 17281. 야구
  • [BOJ] 백준 24042. 횡단보도
동구름이
동구름이
동구름이
동구름
동구름이
전체
오늘
어제
  • 분류 전체보기 (178) N
    • Java (63)
      • Java 를 파헤쳐보자 (13)
      • BOJ (45)
      • 프로그래머스 (3)
      • SWEA (1)
      • Java GUI (1)
    • JavaScript (17)
      • JS를 파헤쳐보자 (7)
      • 프로그래머스 (7)
      • JS 학습 정리 (1)
    • Backend (33) N
      • Spring (3)
      • HTTP (7)
      • 프로젝트 (10)
      • MySQL (6) N
      • Redis (3)
      • Elastic Search (1)
      • 인증, 인가 (3)
    • CS (57)
      • 운영체제 (35)
      • Network (22)
    • Git (2)
    • 개발 관련 이것저것 (2)
    • etc (1)
    • 독서 (0)
    • 사설 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BOJ
  • 네트워크
  • 운영체제
  • 프로그래머스
  • 큐
  • 레디스
  • 인프런
  • 한양대
  • 스택
  • JCF
  • 구현
  • 김영한
  • Java
  • OS
  • 모든 개발자를 위한 HTTP 웹 기본 지식
  • 자바스크립트
  • 자바
  • 백준
  • 이석복
  • 반효경

최근 글

hELLO · Designed By 정상우.v4.2.2
동구름이
[BOJ] 백준 3584. 가장 가까운 공통 조상
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.