13. 그래프 - 최소 공통 조상(LCA)

기본편

개념

 

• 정의: 두 노드의 공통된 조상 중 가장 가까운 조상을 찾는 문제

 

• 동작 과정:
  • 모든 노드에 대한 깊이(depth) 계산
  • 최소 공통 조상을 찾을 두 노드를 확인 - LCA(a,b) 연산에 대하여 아래 과정을 반복
    • 먼저 두 노드의 깊이(depth)가 동일하도록 거슬러 올라감
    • 이후 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감
• 시간 복잡도: O(N) - 매 쿼리마다 부모 방향으로 거슬러 올라가기 때문에
• 언제 사용?:
  • m번의 LCA연산으로 총 O(MN) 시간 복잡도가 괜찮을 경우 
  • 메모리 여유가 없을 경우

 

구현

//n: 노드 개수, m: LCA연산 횟수
static int n, m;
static int[] parent = new int[n+1]; // 부모 노드에 대한 정보
static int[] depth = new int[n+1]; // 각 노드까지의 깊이
static boolean[] checked = new boolean[n+1]; // 깊이 계산 여부
static ArrayList<Integer>[] graph = new ArrayList[n+1]; // 그래프 정보

 

1. 모든 노드 깊이(depth) 계산

DFS를 이용해 모든 노드에 대하여 깊이(depth)를 계산

코드

// 깊이(depth)를 구하는 함수:
// x - 노드 번호
// d - 깊이
public static void dfs(int x, int d) {
	//자신(x)의 깊이를 d로 지정 
    checked[x] = true;
    depth[x] = d;
    
    //자신(x)의 자식 노드(y)에 대해서 처리 진행(재귀)
    for (int y : graph[x]) {
        if (checked[y]) continue; // 이미 깊이를 구했다면 넘어가기
        parent[y] = x;
        dfs(y, d + 1);
    }
}

 

 

2. LCA(A, B) 연산 진행

먼저 두 노드의 깊이를 맞춤

 

 

부모가 같아질 땔까지 거슬러 올라감

 

코드

// 최소 공통 조상을 찾는 함수
public static int lca(int a, int b) {
    // 먼저 깊이가 동일하도록 조정
    while (depth[a] != depth[b]) {
        if (depth[a] > depth[b]) a = parent[a];
        else b = parent[b];
    }
    // 노드가 같아질 때까지 올라가기
    while (a != b) {
        a = parent[a];
        b = parent[b];
    }
    return a;
}

 

최종 코드

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

public class Main {
    static int n, m;
    static int[] parent; // 부모 노드에 대한 정보
    static int[] depth; // 각 노드까지의 깊이
    static boolean[] checked; // 깊이 계산 여부
    static ArrayList<Integer>[] graph; // 그래프 정보
   
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        
        //각 테이블 정보 초기화
        parent = new int[n+1];
    	depth = new int[n+1];
    	checked = new int[n+1];
        
        // 그래프 초기화
    	graph = new ArrayList[n+1];
        for (int i = 0; i < MAX; i++) {
            graph[i] = new ArrayList<>();
        }
        //그래프 정보 입력 받기
        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

		//1. 루트 노드부터 깊이 계산 시작
        dfs(1, 0); 

		//2. LCA 연산 진행
        m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(lca(a, b));
        }
        scanner.close();
    }


    // 깊이를 구하는 함수
    public static void dfs(int x, int d) {
        checked[x] = true;
        depth[x] = d;
        for (int y : graph[x]) {
            if (checked[y]) continue; // 이미 깊이를 계산했다면 넘어가기
            parent[y] = x;
            dfs(y, d + 1);
        }
    }

    // 최소 공통 조상을 찾는 함수
    public static int lca(int a, int b) {
        // 먼저 깊이가 동일하도록 조정
        while (depth[a] != depth[b]) {
            if (depth[a] > depth[b]) a = parent[a];
            else b = parent[b];
        }
        // 노드가 같아질 때까지 올라가기
        while (a != b) {
            a = parent[a];
            b = parent[b];
        }
        return a;
    }

    
}

 

개선편

개념

• 시간복잡도: O(N) -> O(logN)으로 개선
• 방법: 각 노드가 거슬러 올라가는 속도를 빠르게 진행
  • = 2의 제곱 형태로 거슬러 올라감
  • 즉, 모든 노드에 대하여 2^i 번째 부모에 대한 정보를 기록
    • 1차원 부모 테이블(parent[k]) -> 2차원 부모 테이블(parent[k][i])로 확장

15번 노드의 부모 테이블(parent[15])의 값 = [11, 5, 1]

 

 

구현

//n: 노드 개수, m: LCA연산 횟수
static int n, m;
//@@ 변경: 1차원 부모 테이블 -> 2차원 부모 테이블
static int[][] parent = new int[n+1][n+1]; // 부모 노드에 대한 정보
static int[] depth = new int[n+1]; // 각 노드까지의 깊이
static boolean[] checked = new boolean[n+1]; // 깊이 계산 여부
static ArrayList<Integer>[] graph = new ArrayList[n+1]; // 그래프 정보

 

1. 모든 노드 깊이(depth) 계산

DFS를 이용해 모든 노드에 대하여 깊이(depth)를 계산

코드

// 깊이(depth)를 구하는 함수
public static void dfs(int x, int d) {
    checked[x] = true;
    depth[x] = d;
    for (int y : graph[x]) {
        if (checked[y]) continue; // 이미 깊이를 구했다면 넘어가기
        parent[y][0] = x; //@@변경: parent[y] -> parent[y][0]
        dfs(y, d + 1);
    }
}

//@@추가: 전체 부모 관계를 설정하는 함수
public static void setParent() {
    dfs(1, 0); // 루트 노드는 1번 노드로 시작
    
    //2^i 앞에 있는 부모 정보 기록: 1,2,4,8....
    for (int i = 1; i < LOG; i++) {
        for (int j = 1; j <= n; j++) {
            parent[j][i] = parent[parent[j][i - 1]][i - 1];
        }
    }
}

 

2. LCA(A, B) 연산 진행

먼저 두 노드의 깊이를 맞춤

 

부모가 같아질 땔까지 거슬러 올라감

이때 2의 제곱꼴로 올라감

코드

// 최소 공통 조상(LCA)을 찾는 함수
public static int lca(int a, int b) {
    // 더 깊은 노드를 b로 설정
    if (depth[a] > depth[b]) {
        int temp = a;
        a = b;
        b = temp;
    }
    // 먼저 깊이가 동일하도록 조정
    for (int i = LOG - 1; i >= 0; i--) {
        if (depth[b] - depth[a] >= (1 << i)) {
            b = parent[b][i];
        }
    }
    // 부모가 같아질 때까지
    if (a == b) return a;
    for (int i = LOG - 1; i >= 0; i--) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }
    return parent[a][0];
}

 

최종 코드

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

public class Main {
    static final int MAX = 100001;
    static final int LOG = 21; // 2^20 = 1,000,000
    static int n, m;
    static int[][] parent = new int[MAX][LOG]; // 부모에 대한 정보
    static int[] depth = new int[MAX]; // 각 노드까지의 깊이
    static boolean[] checked = new boolean[MAX]; // 각 노드의 깊이가 계산되었는지 여부
    static ArrayList<Integer>[] graph = new ArrayList[MAX]; // 그래프 정보
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();

        for (int i = 0; i < MAX; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

        setParent();

        m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(lca(a, b));
        }

        scanner.close();
    }

    // 깊이(depth)를 구하는 함수
    public static void dfs(int x, int d) {
        checked[x] = true;
        depth[x] = d;
        for (int y : graph[x]) {
            if (checked[y]) continue; // 이미 깊이를 구했다면 넘어가기
            parent[y][0] = x;
            dfs(y, d + 1);
        }
    }

    // 전체 부모 관계를 설정하는 함수
    public static void setParent() {
        dfs(1, 0); // 루트 노드는 1번 노드로 시작
        for (int i = 1; i < LOG; i++) {
            for (int j = 1; j <= n; j++) {
                parent[j][i] = parent[parent[j][i - 1]][i - 1];
            }
        }
    }

    // 최소 공통 조상(LCA)을 찾는 함수
    public static int lca(int a, int b) {
        // 더 깊은 노드를 b로 설정
        if (depth[a] > depth[b]) {
            int temp = a;
            a = b;
            b = temp;
        }
        // 먼저 깊이가 동일하도록 조정
        for (int i = LOG - 1; i >= 0; i--) {
            if (depth[b] - depth[a] >= (1 << i)) {
                b = parent[b][i];
            }
        }
        // 부모가 같아질 때까지
        if (a == b) return a;
        for (int i = LOG - 1; i >= 0; i--) {
            if (parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];
    }

    
}