[백준 11437] 알고리즘 115일차 : LCA

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

11437번: LCA

C++ BFS

그래프에서 최소 공통 조상 찾는 문제이다.

LCA 알고리즘은 기본틀이 있는 것 같아서 로직 힌트를 얻고 풀기 시작했다.

공책에 미리 로직 정리하고 코드 쓰면 좋은 점 : 정신적 스트레스가 적음 (?)

 

접근방법

필요한 자료구조

- 그래프 연결정보를 담고 있는 인접 리스트

- 노드 방문 정보를 담고 있는 배열

- bfs 큐

<bfs로 탐색하면서 값을 저장>

- 노드의 부모노드 정보를 담고있는 배열

- 노드의 깊이를 잠고 있는 배열

 

1. 인접 리스트 생성

우선 이 문제는 부모, 자식 관계 명시 없이 그냥 연결된 노드를 입력으로 받아서 인접 리스트 생성할때 무방향그래프식으로 만들었다.

 

2. BFS로 탐색하면서 부모노드와 깊이 정보 계산하기

*부모 자식 관계를 모르기 때문에 visit 배열로 방문여부를 체크해준다.

 

3. 두 노드의 공통 조상 탐색

두 노드가 주어지면 두 노드의 깊이를 비교해서 깊이가 같아질 때 까지 깊이가 깊은 노드를 그 노드의 부모노드로 교체한다.(깊이를 줄인다)

현재 두 노드가 같아질때까지 반복한다.

두 노드의 깊이가 같은데도 현재 두 노드가 같지 않다면 두 노드 모두 부모노드로 교체한다.

모든 노드의 공통조상은 루트노드 이므로 반복문은 반드시 종료된다.

 

오답노트

bfs에서 큐 쓰는데 pop할때 q.front() 해야되는데 q.back() 해서 .. 곤란..

벡터쓰는게 습관이 됐나보다

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> adj(50001);
int parents[50001];
int depths[50001];
int visit[50001];
queue<int> q;

int main(){
    //input & init
    int N;
    cin >> N;
    
    for(int i = 0 ; i < N-1 ; i++){
        int p, c;
        cin >> p >> c;
        adj[p].push_back(c);
        adj[c].push_back(p);
    }
    
    //bfs : 부모노드, 깊이 계산
    parents[1] = 0;
    depths[1] = 1;
    q.push(1);
    while(!q.empty()){
        int parent = q.front();
        q.pop();
        visit[parent] = 1;
        for(int i = 0 ; i < adj[parent].size() ; i++){
            int child = adj[parent][i];
            if(!visit[child]){
                parents[child] = parent;
                depths[child] = depths[parent]+1;
                q.push(child);
            }
        }
    }
    
    //공통조상 탐색
    //input
    int M;
    cin >> M;
    
    for(int i = 0 ; i < M ; i++){
        int a, b;
        cin >> a >> b;
        int result = 1;
        while(true){
            if(a == b){
                result = a;
                break;
            }else{
                if(depths[a] > depths[b]){
                    a = parents[a];
                }else if(depths[a] < depths[b]){
                    b = parents[b];
                }else{
                    a = parents[a];
                    b = parents[b];
                }
            }
        }
        cout << result << "\n";
    }
    
    return 0;
}