[그래프] LCA2

백준 11438 LCA2

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

아직 소스 개선의 여지가 많이 남아있음.

package com.company;

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

public class Main {

    static int[][] parent; // parent[a][b] a의 2^b번째 부모
    static ArrayList<Integer>[] adj; //트리
    static int[] depth;


    public static void main(String[] args) throws Exception{
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //노드개수

        adj = new ArrayList[N+1];
        parent = new int[N+1][21];
        depth = new int[N+1];

        StringTokenizer st;
        for(int i=0; i<N-1; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            if(adj[ v1 ]==null) adj[ v1 ] = new ArrayList<>();
            if(adj[ v2 ]==null) adj[ v2 ] = new ArrayList<>();
            adj[ v1 ].add(v2);
            adj[ v2 ].add(v1);
        }

        bfs();
        fill(N);

        int M = Integer.parseInt(br.readLine());
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            System.out.println( lca(v1, v2) );
        }
    }


    //두 노드의 공통조상을 반환
    static int lca(int v1, int v2){

        //더 깊은게 v1
        if(depth[v1] < depth[v2]){
            int temp = v1;
            v1 = v2;
            v2 = temp;
        }

//        System.out.printf("[%d]:%d, [%d]:%d diff:%d\n",v1, depth[v1], v2, depth[v2], (depth[v1] - depth[v2]));

        //더 깊은 v1을 2승씩 점프하며 두 노드의 depth를 맞춘다
        for(int i=20; 0<=i; i--) {
            if( Math.pow(2,i) <= depth[v1] - depth[v2] ) {
//            System.out.println("점프:"+i);
                v1 = parent[v1][i];
            }
        }

//        System.out.println("동일뎁스: " + v1);

        //높이 맞췄는데 두 수가 같음
        if(v1==v2) return v1;

        //두 노드를 같이 2승씩 점프시키며 공통부모 바로 아래까지 올림
        for(int i=20; 0<=i; i--) {
            if(parent[v1][i] != parent[v2][i]) {
                v1 = parent[v1][i];
                v2 = parent[v2][i];
            }
        }

        return parent[v1][0];
    }

    static void fill(int N){

        for(int i=1; i<=20; i++){
            for(int n=1; n<=N; n++){
                parent[n][i] = parent[ parent[n][i-1] ][i-1];
            }
        }

    }

    static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        int dep=0;


        while (!q.isEmpty()){

            int qSize = q.size();
            for(int i=0; i<qSize; i++){
                int vertex = q.poll();
                depth[vertex]=dep;

                if(adj[vertex] == null) continue; //자손노드가 없음

                //부모정보를 지정.
                for(int j=0; j<adj[vertex].size(); j++){
                    
                    //노드간 양방향으로 연결되어 있어서 무한대로 이어지는 거 체크
                    if( adj[vertex].get(j)==parent[vertex][0]){
                        continue;
                    }

                    parent[ adj[vertex].get(j) ][0] = vertex; //내 자손의 부모는 나다
                    q.offer( adj[vertex].get(j) ); //큐에 삽입
                }
            }
            dep++;
        }
    }
}

노드 양방향 처리를 안해서 오류가 있었음.

//노드간 양방향으로 연결되어 있어서 무한대로 이어지는 거 체크
if( adj[vertex].get(j)==parent[vertex][0]){
           continue;
}

양방향으로 1->2, 2->1 로 처리해놓으면 무한대로 이어진다. 

숫자가 작은 노드가 부모세대가 되는 법칙이 있는 것은 아니므로. 한 방향으로 해서도 안됨. 

일단 양방향으로 해놓고 루프가 생기면 continue로 무효처리함.

자신의 부모 = 자신의 자손 이면 루프니까 무효.

visited쓰면 됨..(2019.2.27)

높이 맞춰주는 부분은 이렇게 고쳐도 똑같음

        //더 깊은 v1을 2승씩 점프하며 두 노드의 depth를 맞춘다
        for(int i=20; 0<=i; i--) {
            if( Math.pow(2,i) <= depth[v1] - depth[v2] ) {
//            System.out.println("점프:"+i);
                v1 = parent[v1][i];
            }
        }

        for(int i=20; 0<=i; i--) {

        if(depth[v2] <= depth[ parent[v1][i] ]) {

        v1 = parent[v1][i];

        }

        }

다시 푼거(2019 2.27)

package LCA2;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N; //노드개수
    static int M; //쌍의 수
    static List<Integer>[] map;
    static boolean[] visited;
    static int[] depth;
    static int[][] parent; //parent[a][b] a의 2^b번째 조상

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new ArrayList[N+1];
        visited = new boolean[N+1];
        depth = new int[N+1];
        parent = new int[N+1][21];


        for(int i=1; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if(map[a]==null) map[a] = new ArrayList<>();
            if(map[b]==null) map[b] = new ArrayList<>();

            map[a].add(b);
            map[b].add(a);
        }

        bfs();
        fillParent();

        M = Integer.parseInt(br.readLine());
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            System.out.println( lca(a,b) );
        }
    }

    static int lca(int a, int b){

        int low, high;

        if(depth[a] < depth[b]){ low=b; high=a; }
        else { low=a; high=b; }

        //낮은 애를 올려서 높이를 맞춰준다
        for(int i=20; 0<=i; i--){
            int diff = depth[low] - depth[high];
            if(Math.pow(2, i) <= diff){
                low = parent[low][i];
            }
        }

//        System.out.printf("low:%d(%d) high:%d(%d)",low,depth[low],high,depth[high]);

        //높이만 맞췄는데 같아져버림
        if( low == high )return high;

        //목표지점 한칸 아래까지 함께 점프
        for(int i=20; 0<=i; i--){
            if(parent[low][i] != parent[high][i]){
                low = parent[low][i];
                high = parent[high][i];
            }
        }

        //남은한칸 마저 점프
        high = parent[high][0];
        //점프 후
//        System.out.printf("[before]low:%d(%d)", low, depth[low]);

        return high;
    }

    static void fillParent(){

        //2^20 = 1,000,000
        for(int b=1; b<=20; b++){
            for(int a=1; a<=N; a++) {
                parent[a][b] = parent[ parent[a][b-1] ][ b-1 ];
            }
        }
    }


    static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visited[1] = true;
        int d=0;


        while (!q.isEmpty()){
            d++;

            int qSize = q.size();
            for(int i=0; i<qSize; i++){
                int now = q.poll();

                if(map[now]==null) continue;

                int mSize = map[now].size();
                for(int j=0; j<mSize; j++){

                    int next = map[now].get(j);
                    if(visited[next]==false){
                        parent[next][0] = now;
                        q.add(next);
                        visited[next]=true;
                        depth[next] = d;
                    }
                }
            }//for

        }
    }
}