공부 100일차: 백준 11437번 LCA 자바 java ☆실패

11437 LCA

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

11437번: LCA

 

 

 

---

백준 11437번 문제 LCA

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

LCA란 Lowest Common Ancestor의 약자로, 최소 공통 조상이라는 의미다

클릭하면 이미지 출처로 이동

이러한 트리 구조 예시의 경우, 노드 9와 11의 최소 공통 조상(LCA)은 2다

 

조상을 구하기 위한 알고리즘을 생각해보면

1. 모든 노드의 깊이를 계산한다 (DFS 이용)
2. LCA를 구해야 하는 두 노드를 구한다 
　　① 두 노드의 깊이가 같아지도록 거슬러 올라간다
　　② 깊이가 같아졌으면, 부모가 같아질 때까지 같은 크기로 부모의 방향으로 거슬러 올라간다
3. 모든 LCA 연산에 대해 2번 과정을 반복한다

 

라고 볼 수 있다

참고: https://www.youtube.com/watch?v=O895NbxirM8 

 

 

참고 블로그: https://iamheesoo.github.io/blog/algo-boj11437

자꾸 인덱스 범위 벗어났다고(ArrayList인데 왜..?) 뜬 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Day72BOJ11437Fail {
    static int n;
    static ArrayList<ArrayList<Integer>> tree;
    static int[] depth;
    static int[] parent;
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
        
        // 트리 생성
        tree = new ArrayList<>();
        for(int i = 0; i <= n; i++) {
            tree.add(new ArrayList<Integer>());
        }
        
        StringTokenizer st = null;
        for(int i = 0; i < n - 1; i++) { //주어진 숫자로 노드 연결
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            tree.get(a).add(b);
            tree.get(b).add(a);
        }
        
        depth = new int[n+1];
        parent = new int[n+1];
        // 2. 대상이 되는 두 노드 구하기
        dfs(1,1);
        int 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(solve(a,b));
        }
    }
    
    // 1. 모든 노드의 깊이 계산 (dfs 이용)
    public static void dfs(int node, int currentDepth) {
        depth[node] = currentDepth;
        
        for(int child: tree.get(node)) {
            if(depth[child] == 0) {    //깊이 계산이 안 됐다면(자식 노드라면)
                dfs(child, currentDepth++);    // 깊이+1
                parent[child]=node;
            }
        }
    }
    
    public static int solve(int a, int b) {
        // 2-1. 두 노드의 깊이가 같아지도록
        while(depth[a] > depth[b]) {    // 노드 a가 더 밑에 있다면
            a = parent[a];
        }
        while(depth[a] < depth[b]) {    // 노드 b가 더 밑에 있다면
            b = parent[b];
        }
        
        
        // 2-2. 부모가 같아질 때까지 부모 방향으로 거슬러 올라가기
        while(a != b) {    // 같은 층이지만 부모가 다르다면
            a = parent[a];
            b = parent[b];
        }
        
        return a;
    }
 
}

 

 

 

 

---

시간이 모자라서 내일 다시 해야 한다..

내일 차근차근 다시 살펴볼 예정.. dfs도 공부해야 하긴 했으니까 마음 편하게 먹고 찬찬히 봐야겠다

 

+여전히 안 보여서 일단 보류.. ㅠㅠ 주말에 시간여유 많을 때 보기로..