[ 트리 ] LCA(백준 11437, 11438)

[ STUDY ]/CodingTest

[ 트리 ] LCA(백준 11437, 11438)

김강니 2024. 11. 14. 18:55

LCA(최소 공통 조상)

트리 그래프에서 임의의 두 노드를 선택했을 때 각각 자신을 포함해 거슬러 올라가다 처음 공통으로 만나게 되는 부모 노드

💡 최소 공통 조상의 핵심 이론

ⓐ 일반적인 최소 공통 조상 구하기

트리의 높이가 크지 않을 때는 일반적인 방법으로 구한다.

1️⃣ 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다.

2️⃣ 만약, 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 depth를 맞춰준다.

3️⃣ 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.
이때 처음 만나는 노드가 최소 공통 조상이 된다.

ⓑ 최소 공통 조상 빠르게 구하기

트리의 높이가 매우 커질 경우, 시간 제약 문제에 직면할 수 있다. 이럴 때 사용하는 것이 '최소 공통 조상 빠르게 구하기'이다.

핵심은 기존에 한단계씩 올리던 방식에서 2^K씩 올라가서 비교하는 방식이다. -> 2^K번째 위치의 부모 노드까지 저장해야함.

1️⃣ 부모 노드 저장 배열 만들기

배열에서 K는 '트리의 깊이 > 2^K'를 만족하는 최댓값이다.

부모 노드 배열의 정의
P[K][N] = N번 노드의 2^K번째 부모의 노드 번호

부모 노드 배열의 점화식
P[K][N] = P[K-1][ P[K-1][N] ]

2️⃣ 선택된 두 노드의 깊이 맞추기

기존에 한 단계씩 맞췄던 깊이를 2^K단위로 넘어가면서 맞춘다.

3️⃣ 최소 공통 조상 찾기

공통 조상을 찾는 작업 역시 한단계가 아닌 2^K단위로 점프하면서 맞춘다.

K값을 1씩 감소하면서 P배열을 이용해 최초로 두 노드의 부모가 달라지는 값을 찾는다.

K가 0이 될 때까지 반복하고 종료 후

이동한 2개의 노드가 같은 노드라면, 해당 노드가 최소 공통 조상
이동한 2개의 노드가 다른 노드라면, 해당 노드 바로 위의 부모 노드가 최소 공통 조상이다.

11437 : LCA

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

입력	출력
15 1 2 1 3 2 4 3 7 6 2 3 8 4 9 2 5 5 11 7 13 10 4 11 15 12 5 14 7 6 6 11 10 9 2 6 7 6 8 13 8 15	2 4 2 1 3 1

문제 풀이

일반적인 최소 공통 조상 구하기로 풀어봤당

실행 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Map;
import java.util.StringTokenizer;

public class P11437_LCA {
    static int N, M;
    static int[][] parent; //0: 부모 노드, 1: 깊이(Depth)
    static boolean[] visited; //DFS 사용시에 방문 여부 배열
    static ArrayList<Integer>[] lists;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine()); //정점의 갯수
        visited = new boolean[N + 1]; //방문 배열
        parent = new int[2][N + 1]; //부모와 깊이를 저장할 배열
        parent[0][1] = 1; parent[1][1] = 0; //루트노드의 부모를 자신과 깊이를 0으로 설정
        lists = new ArrayList[N + 1];
        
        //인접리스트 만들기
        for(int i = 1; i <= N; i++) {
            lists[i] = new ArrayList<>();
        }

        //인접리스트 데이터 채우기
        for(int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            lists[a].add(b);
            lists[b].add(a);
        }

        //DFS로 부모와 깊이 저장
        DFS(1);

        int M = Integer.parseInt(br.readLine()); //LCA찾을 횟수

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()); //노드1
            int b = Integer.parseInt(st.nextToken()); //노드2
            System.out.println(LCA(a, b));
        }
    }

    //최초 공통 조상 찾기
    private static int LCA(int a, int b) {
        int father = 0; //공통 조상
        if(parent[1][a]<parent[1][b]) {
            int sub = parent[1][b] - parent[1][a]; // 차이만큼만 올라가면 됨
            for(int i = 0; i<sub;i++){
                b = parent[0][b];
            }
        }else if(parent[1][a]>parent[1][b]) {
            int sub = parent[1][a] - parent[1][b]; // 차이만큼만 올라가면 됨
            for(int i = 0; i<sub;i++){
                a = parent[0][a];
            }
        }
        //같은 경우
        if(parent[1][a]==parent[1][b]){
            while(a!=b){
                a = parent[0][a];
                b = parent[0][b];
            }
        }
        return a;
    }

    private static void DFS(int i) {
        if(visited[i]) return;
        visited[i] = true;
        for(int v : lists[i]) { //방문안했다는건 v가 i의 자식이라는 거
            if(!visited[v]) {
                parent[0][v] = i; //부모를 저장
                parent[1][v] = parent[1][i] + 1; //부모의 깊이 + 1
                DFS(v);
            }
        }
    }
}

11438 : LCA 2

문제

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

입력	출력
15 1 2 1 3 2 4 3 7 6 2 3 8 4 9 2 5 5 11 7 13 10 4 11 15 12 5 14 7 6 6 11 10 9 2 6 7 6 8 13 8 15	2 4 2 1 3 1

문제 풀이

최소 공통 조상 빠르게 찾기!!ㅋㅋ
아무래도어려움

실행 코드

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

public class P11438_LCAFast {
    static int N, M, K;
    static int[][] parent; // 부모 노드 배열
    static int[] depth;
    static boolean[] visited; //DFS 사용시에 방문 여부 배열
    static ArrayList<Integer>[] lists;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine()); //정점의 갯수
        visited = new boolean[N + 1]; //방문 배열
        depth = new int[N + 1]; //깊이 배열

        //k구하기 temp에 2씩 곱해서 N보다 작을 때까지
        int temp = 1;
        K = 0;
        while(temp <= N) {
            temp<<=1;
            K++;
        }

        parent = new int[K][N + 1]; //부모를 저장할 배열
        lists = new ArrayList[N + 1];

        K = (int) Math.ceil(Math.log(N) / Math.log(2)); // 2^k < 트리의 깊이을 만족하는 최댓값

        //인접리스트 만들기
        for(int i = 1; i <= N; i++) {
            lists[i] = new ArrayList<>();
        }

        //인접리스트 데이터 채우기
        for(int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            lists[a].add(b);
            lists[b].add(a);
        }

        //DFS로 [0] 부모저장
        DFS(1);

        //2^k 부모 저장
        for(int i = 1;i<K;i++){
            for(int j = 1;j<=N;j++){
                parent[i][j] = parent[i-1][parent[i-1][j]];
            }
        }

        M = Integer.parseInt(br.readLine()); //LCA 찾을 횟수

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()); //노드1
            int b = Integer.parseInt(st.nextToken()); //노드2
            System.out.println(LCA(a, b));
        }
    }

    //최초 공통 조상 찾기
    private static int LCA(int a, int b) {
        //a가 더 깊어도 b와 바꿔서 b가 더 깊게
        if(depth[a]>depth[b]) {
            int temp = a;
            a = b;
            b = temp;
        }

        //깊이 맞추기
        for(int k = K-1; k >= 0; k--) {
            if((1 << k) <= depth[b]-depth[a]) {
                b = parent[k][b];
            }
        }

        if (a == b) return a; // 같은 경우 바로 반환

        //조상 찾기
        for(int k = K-1; k >= 0; k--) {
            if(parent[k][a] != parent[k][b]) {
                a = parent[k][a];
                b = parent[k][b];
            }
        }

        if(a==b) return a;
        else return parent[0][a];
    }

    private static void DFS(int i) {
        if(visited[i]) return;
        visited[i] = true;
        for(int v : lists[i]) { //방문안했다는건 v가 i의 자식이라는 거
            if(!visited[v]) {
                parent[0][v] = i; //부모를 저장
                depth[v] = depth[i] +1 ; //깊이 저장
                DFS(v);
            }
        }
    }
}

'[ STUDY ] > CodingTest' 카테고리의 다른 글

[ 동적 계획법 ] DP(Dynamic Programming, 백준 2747, 11726) (0)	2024.11.14
[ 조합 ] 조합(백준 11050) (1)	2024.11.14
[ 트리 ] 세그먼트 트리(백준 2042) (5)	2024.11.14
[ 트리 ] 이진 트리(백준 1191) (0)	2024.11.13
[ 트리 ] 트리🎄(백준 11725) (0)	2024.11.13

현재글[ 트리 ] LCA(백준 11437, 11438)

나다김강니

험나난세상속에뛰어든건나니까암오케....

오블완, React, 모두의 리눅스, redux-persist, HTTP, Troubleshooting, VMware Fusion, CodeUp, dp, spring boot, dfs, 다익스트라, Redux, 백준, 티스토리챌린지, linux, Spring Security, BFS, 우선순위 큐, JWT,

Today :
Yesterday :

나다김강니