[SWEA] 1855 영준이의 진짜 BFS JAVA

문제링크

SW Expert Academy

 

1. 문제의 유형 및 이해

BFS, LCA(최소 공통 조상)

최소 공통 조상(LCA, Lowest Common Ancestor)

주어진 트리에서 BFS를 통해 그래프를 탐색하고자 합니다.

영준이는 직접 트리를 방문해야 하기 때문에 영준이는 정해진 BFS 순서대로 트리를 탐색하게 된다고 할 때,

영준이는 과연 몇 개의 간선을 지나고 나서야 탐색을 끝 마칠 수 있을까?

[그림1 ] 예시

탐색을 할 때는 "작은 번호 부터" 순서대로 큐의 뒤쪽에 넣는 방식으로 탐색이 진행된다.

 

구하고자 하는 값은 결국 어떠한 노드와 노드 사이의 거리를 계산하는 문제입니다.

트리에서 노드와 노드 사이의 거리를 계산하기 위해서는 어떻게 해야할까요.

LCA를 활용하면 두 노드의 거리를 계산할 수 있습니다. LCA가 두 정점이 처음 만나는 지점이기 때문입니다.

 

2. 문제 접근 방법

BFS 탐색 순서로 진행된다고 하였기 때문에 BFS를 통해 탐색 순서를 받아옵니다.

탐색순서와 LCA를 활용하여 두 정점간의 거리를 계산 할 수 있습니다.

 

이 때, LCA를 구현하는 데에 조금만 더 생각해보도록 합시다.

문제에서의 노드 개수는 $10^5$ 개로 주어지고 있습니다.

일반적인 방법으로 LCA를 구하는 데에 O(N)의 시간복잡도를 가지게 되고,

노드 N개에 대해 N-1 번 반복하여 LCA를 구해야 합니다.

그래서 LCA를 O(N)에 구하게 된다면, O($N^2$) 시간복잡도를 가져 시간초과가 발생하게 됩니다.

 

그렇기 때문에 LCA를 조금 더 빠르게 구할 수 있는 "세그먼트 트리를 활용한 방법" 과 "dp를 활용한 방법" 중에서 dp를 활용한 방법을 사용하여 구현하도록 합니다.

dp를 활용할 경우에 전처리 시간에 O(NlogN) 그리고 각 질의에 응답하는 데에 O(logN)시간을 가지고 있습니다.

총 질의가 N-1개가 들어오기 때문에 전처리 시간과 질의에 응답하는 시간을 계산하면

O(NlogN)시간에 문제를 해결할 수 있게 됩니다.

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

/**
 * 영준이의 real BFS
 * bfs 순서대로 진행을 하면서 거리를 측정하여 이동거리를 계산한다.
 * 이 때 어떠한 u에서 v로 갈 때는 항상 공통조상을 거쳐서 지나가게 된다.
 * 그렇게 되면 u에서 공통조상까지의 거리 + v에서 공통조상까지의 거리가 더해지게 된다.
 * 필요한건 현재와 이전값이 필요하다.
 * Point는 어차피 BFS를 한번 해야합니다.
 * 이 때 기록을 해 두고, 값 두개씩 가져와서 계산하는게 나을 듯합니다.
 * root는 항상 1이고, 타색하는 노드는 작은 번호부터 탐색한다.
 * */
public class Solution {
    //LCA를 구해야합니다.
    //parent가 정해져서 나온다.
    static ArrayList<Integer>[] tree;
    static int[] depth;
    static int[][] parent;
    static int maxLevel;
    static int[] order;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int tt = 1; tt <= T; tt++) {
            sb.append('#').append(tt).append(' ');
            N = Integer.parseInt(br.readLine());
            maxLevel = calcMaxLevel(N) + 1;
            depth = new int[N+1];
            parent = new int[N + 1][maxLevel];
            tree = new ArrayList[N+1];
            order = new int[N];
            for (int i = 0; i < N + 1; i++) tree[i] = new ArrayList<Integer>();

            st = new StringTokenizer(br.readLine());
            for(int i= 2;i<N+1;i++){
                int p = Integer.parseInt(st.nextToken());
                parent[i][0] = p;
                tree[p].add(i);
            }

            //BFS with height And parent init
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(1);
            int idx =0 ;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                order[idx++] = cur;
                //parent 배열 계산
                for(int i =1;i<maxLevel;i++){
                    parent[cur][i] = parent[parent[cur][i-1]][i-1];
                }
                for (int nxt : tree[cur]) {
                    depth[nxt] = depth[cur] +1;
                    queue.add(nxt);
                }
            }
            //LCA  항상 i가 i+1보다 depth가 낮음. 항상 always
            //구한 bfs순서대로 lca 질의를 통해 답을 알아내도록 합시다.
            long ans =0;
            for(int i =0;i<N-1;i++){
                int lca = LCA(order[i], order[i + 1]);
                ans += (depth[order[i]] - depth[lca]) + (depth[order[i + 1]] - depth[lca]);
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
    public static int LCA(int a, int b){
        //높이를 맞춰주어야겟죠
        for(int i =maxLevel;i>=0;i--){
            if(((depth[b] - depth[a])&1<<i)>0){
                b = parent[b][i];
            }
        }
        if(b==a) return a;
        for(int i = maxLevel-1;i>=0;i--){
            if (parent[a][i] != parent[b][i]) {
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        return parent[a][0];
    }


    public static int calcMaxLevel(int n) {
        double log2 = Math.log(n)/Math.log(2);
        return (int) Math.ceil(log2);
    }
}

//     시간초과 LCA
//    public static int solve(int a, int b) {
//        int cnt =0;
//        if(depth[a] > depth[b]){
//            while(depth[a] != depth[b]){
//                a = parent[a];
//                cnt++;
//            }
//        }else if(depth[a] < depth[b]){
//            while (depth[a] != depth[b]) {
//                b = parent[b];
//                cnt++;
//            }
//        }
//        while(a != b){
//            a = parent[a];
//            b = parent[b];
//            cnt += 2;
//        }
//        return cnt;
//    }

 

 

3. Review

정점간의 거리를 어떻게 빨리 계산할 수 있는가 하는 문제였습니다.

공통 조상 즉, 처음으로 겹치는 부분을 찾아서 가면 되겠다라고 직관적으로 이해하기는 쉬우나

LCA 알고리즘을 몰랐더라면, 또는 알고있더라도 많은 질의에 응답할 수 있도록 최적화하지 않는다면

문제를 풀기에 꽤나 어려운 문제였을 것 같습니다.