[백준/JAVA] 11437번: LCA

🔺 문제

11437번: LCA

 

 

🔺 코드

- 틀림 (시간 초과)

import java.util.*;
import java.io.*;
 
public class Main {
    static ArrayList<Integer>[] tree; // 인접 리스트
    static int[] depth;         // 노드 깊이 배열
    static int[] parent;        // 노드 조상 배열
    static boolean[] visited;   // 방문 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());    // 정점 개수
 
        tree = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            tree[i] = new ArrayList<Integer>();
        }
        
        // 인접 리스트에 그래프 데이터 저장
        for(int i = 0 ; i < N - 1 ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(st.toToken());
            int e = Integer.parseInt(st.toToken());
            tree[s].add(e);
            tree[e].add(s);
        }
        
        depth   = new int[N + 1];
        parent  = new int[N + 1];
        visited = new boolean[N + 1];
        
        BFS(1); // BFS 이용해 depth 계산
        
        int M = Integer.parseInt(br.readLine()); // 조상 알고싶은 쌍 개수
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.toToken());
            int b = Integer.parseInt(st.toToken());
            int result = LCA(a, b);
            System.out.println(result);   
        }
    }
    
    // 최소 공통 조상 구하는 메소드
    static int LCA(int a, int b) {
        // 깊이가 더 깊은 쪽을 
        if(depth[a] < depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        
        // 두 노드의 depth 맞추기
        while(depth[a] != depth[b]) {
            a = parent[a];
        }
        // 같은 조상이 나올 때까지 한 칸씩 올리기
        while(a != b) {
            a = parent[a];
            b = parent[b];
        }
        return a;   // 최소 공통 조상 리턴
    }
    
    // BFS ← 목적 : depth 계산
    private static void BFS(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        visited[node] = true;
        
        int level = 0;
        int now_size = 1;
        int cnt = 0;
        
        while(!q.isEmpty()) {
            int from = q.poll();
            
            for(int to : tree[from]) {
                if(!visited[to]) {
                    visited[to] = true;
                    q.add(to);
                    
                    parent[to] = from; // 부모 노드 저장
                    depth[to]  = level;    // 현재 높이 저장
                }
            }
            cnt++;
            
            if(cnt == now_size) {   // 이번 높이에 해당하는 모든 노드를 방문했을 때
                cnt = 0;
                now_size = q.size();
                level++;
            }
        }
    }
}

 

 

- 정답

import java.util.*;
import java.io.*;
 
public class Main {
    static ArrayList<Integer>[] tree; // 인접 리스트
    static int[] depth;         // 노드 깊이 배열
    static int[] parent;        // 노드 조상 배열
    static boolean[] visited;   // 방문 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());    // 정점 개수
        tree = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            tree[i] = new ArrayList<Integer>();
        }
        
        // 인접 리스트에 그래프 데이터 저장
        for(int i = 0 ; i < N - 1 ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            tree[s].add(e);
            tree[e].add(s);
        }
        
        depth   = new int[N + 1];
        parent  = new int[N + 1];
        visited = new boolean[N + 1];
        
        depth[1]  = 1;
        parent[1] = 0;
        
        DFS(1); // DFS 이용해 depth 계산
        
        StringBuilder sb = new StringBuilder();
        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());
            int result = LCA(a, b);
            sb.append(result + "\n");   
        }
        System.out.println(sb);
        br.close();
    }
    
    // 최소 공통 조상 구하는 메소드
    static int LCA(int a, int b) {
        if(depth[a] < depth[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        
        // 두 노드의 depth 맞추기
        while(depth[a] != depth[b]) {
            a = parent[a];
        }
        // 같은 조상이 나올 때까지 한 칸씩 올리기
        while(a != b) {
            a = parent[a];
            b = parent[b];
        }
        return a;   // 최소 공통 조상 리턴
    }
    
    // DFS ← 목적 : depth 계산
    private static void DFS(int node) {
        visited[node] = true;
        
        for(int next : tree[node]) {
            if(!visited[next]) {
               visited[next] = true;
               depth[next]  = depth[node] + 1;    // 현재 높이 저장                
               parent[next] = node; // 부모 노드 저장
               DFS(next);
            }
        }
    }
}

✅ 해결 아이디어
✔ 최소 공통 조상 (LCA)
- 인접 리스트 사용 & DFS 사용

 

 

💥 유의사항

⇨ BFS 쓰면 시간초과가 뜸... 입력이나 주어진 트리의 크기가 큰 경우는 DFS를 사용하자!

 

---

🔺 다른 풀이들

- 상세 과정 설명 굿 (복습용1)

if( !visited[next] ) 하지 않고, if( depth[next] == 0 ) 쓰심

[BOJ] 백준 11437번 LCA 자바 풀이

 

- 개인적으로 제일 깔끔한 풀이..  (복습용2)

[JAVA/백준] 11437번: LCA

 

 

- DFS 활용하심 & 메모리 small

[백준] 11437번 - LCA (java)

 

 

- BFS 활용하셨고, visited 배열이 필요 없당 & 노드 클래스 만들어서 사용하심

98. LCA (백준 11437) [JAVA]

---

💬 느낀 점

이약 어렵구나...

 

 

1회독	2회독	3회독	4회독	5회독
V	230510