글 읽기 - 새로운 시각이 필요합니다.

lms8147 5년 전 3

인접리스트로 트리 구현하기
구현된 트리를 정점 1부터 시작하여 dfs 탐색하면서 tree 부모관계, 최대 깊이 설정
LCA를 구하고자 하는 두개의 정점의 깊이 차이를 2진 비트를 이용해 없애기
같아진 두개의 정점에 대해 2^k 단위로 부모를 찾으며 같아지는 최소한의 부모 찾기

위의 과정으로 구현을 해봤습니다.

채점 결과 틀렸습니다가 나오는데 작성자라 그런지 제 눈엔 오류가 보이질 않네요.

저와 다른 시각으로 보시고 오류가 생길법한 구간을 찾아주시면 감사하겠습니다.

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));

        int n = sc.nextInt();

        ArrayList<Integer>[] tree = new ArrayList[n + 1];
        for (int i = 1; i < n + 1; i++)
            tree[i] = new ArrayList<>();

        for (int e = 0; e < n - 1; e++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            tree[v1].add(v2);
            tree[v2].add(v1);
        }

        int m = sc.nextInt();

        Main main0 = new Main(n, m, tree);

        for (int q = 0; q < m; q++) {
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            main0.solve(v1, v2);
        }


    }

    int n;
    int m;
    int[] parents;
    int[][] dParents;
    int[] depths;
    ArrayList<Integer>[] tree;

    int maxDepth = Integer.MIN_VALUE;

    public Main(int n, int m, ArrayList<Integer>[] tree) {
        this.n = n;
        this.m = m;
        this.parents = new int[n + 1];
        this.depths = new int[n + 1];

        this.tree = tree;
        dfs(1, 0);
        int maxLevel = maxDepth + 1;
        int logLevel = 0;
        while (0 != (maxLevel = maxLevel >> 1)) {
            logLevel++;
        }

        dParents = new int[logLevel + 1][];
        dParents[0] = parents;
        for (int k = 1; k <= logLevel; k++) {
            dParents[k] = new int[n + 1];
            for (int v = 1; v < n + 1; v++) {
                dParents[k][v] = dParents[k - 1][dParents[k - 1][v]];
            }
        }
    }

    public void dfs(int vertex, int depth) {
        depths[vertex] = depth;
        if (maxDepth < depth)
            maxDepth = depth;
        if (parents[vertex] != 0 && tree[vertex].size() == 1) {
            return;
        }

        for (int adjVertex : tree[vertex]) {
            if (parents[vertex] != adjVertex) {
                parents[adjVertex] = vertex;
                dfs(adjVertex, depth + 1);
            }
        }
    }

    public void solve(int v1, int v2) {

        int depthV1 = depths[v1];
        int depthV2 = depths[v2];

        int diff = 0;
        int[] p = {v1, v2};
        int moreDepthV;

        if (depthV1 > depthV2) {
            diff = depthV1 - depthV2;
            moreDepthV = 0;
        } else {
            diff = depthV2 - depthV1;
            moreDepthV = 1;
        }

        /*
         * make parent depth same
         */
        if (diff > 0) {
            int k = 0;
            while (0 != diff) {
                int bit = diff & 1;
                if (bit > 0) {
                    p[moreDepthV] = dParents[k][p[moreDepthV]];
                }
                diff = diff >> 1;
                k++;
            }
        }

        if (p[0] != p[1])
            System.out.println(findLCA(p[0], p[1]));
        else
            System.out.println(p[0]);
    }

    /**
     * find LCA if depth v1 == depth v2
     *
     * @param v1
     * @param v2
     */
    public int findLCA(int v1, int v2) {

        int p1 = dParents[0][v1];
        int p2 = dParents[0][v2];

        if(p1 == p2){
            return p1;
        }else{
            for(int k = 1; k < dParents.length; k++){
                if(dParents[k][v1] == dParents[k][v2]){
                    return findLCA(dParents[k - 1][v1], dParents[k - 1][v2]);
                }
            }
        }

        return 0;
    }
}

lms8147 5년 전 0

감사합니다.

올려주신 예제 덕분에 문제점을 찾았습니다.

2^k 단위로 부모를 찾아 나가기 위해 JUMP 할 수 있는 최대 k를 구하는 곳에 오류가 있더군요.

트리 최대 레벨 보다 같거나 큰 2^k 를 만족하는 k 를 구하기 위해

쉬프트 연산을 써서 카운팅을 하는데 올림 보정을 하지않아

만족하는 2^k 가 없는 경우가 생기네요.

--------------------------------------------------------------

올려주신 다른 LCA 해법도 적용해보겠습니다.

emevoluoyod 4년 전 0

저도 cubelover님 덕분에 런타임 에러 해결했습니다 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

새로운 시각이 필요합니다.

lms8147 5년 전 3

lms8147 5년 전 0

emevoluoyod 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말