[c++] 백준 - lca (그래프 이론)

1. 문제

2. 입 출력

3. 예제 입출력

4. 문제 해설

처음 이 문제를 마주했을 때 나는 대강 풀이법을 들어서 알고 있었다. 따라서 조금 빨리 구현할 수 있었던 거 같다. 

 

그런데 한 가지 고민했던 점은 부모노드와 자식노드를 어떻게 판별하는 것일까였다. 

처음에는 입력의 순서가 부모-자식 순인가 했었지만 다시 생각해보니 부모-자식 순으로 입력이 들어오는 것은 아닌 거 같았다. 처음에 들어오는 입력이 더 클 수도 나중에 들어오는 입력이 더 큰 경우도 존재했기 때문이다. 

 

그래서 그 다음 생각했던 것은 입력의 순서대로 트리가 구성되는 것인가?를 고민해보았다. 

그러면 입력이 어떻게 들어오든 앞선 입력에 존재하는 노드가 부모가 되겠거니 했다. 

 

그래서 양방향으로 벡터에 푸쉬해주었다. 

---

1. 입력 (양방향으로 연결성을 표시)

vector<int> v[50000];
void input() {
	scanf("%d", &N);
    for(int i=0; i < N-1; i++) {
    	int a, b;
    	scanf("%d %d" , &a, &b);
        v[a].push_back(b);
        v[b].push_back(a); // 양방향으로 연결을 부여해주었다. 
    }
    scanf("%d", &M);
    for(int i=0; i < M ;i++){
    	int x, y;
        scanf("%d %d", &x, &y);
        sol(x,y); // 해결 로직 함수 
    }
}

2. 부모 자식 노드 판별

우선 lca를 통해 최소 공통 조상을 판별하려면 각 노드의 depth를 알아야한다. 

따라서 bfs를 통해 depth를 파악해주었다. 

여기서 부모-자식 순서 상관없이 입력받은 인풋들의 부모 - 자식 여부를 판단할 수 있는데 bfs()의 경우 이미 방문한 노드라면 방문하지 않으므로 나중에 등장한 자식 노드의 경우 벡터 안에 부모와의 연결성이 표시되어 있더라도 이미 부모를 방문한 상태이기 때문에 방문하지 않는다. 따라서 부모-자식 관계가 자동으로 설정된다. 

부모를 기록하는 배열에 기록하며 올라간다.

bfs함수는 다음과 같다. 

queue <int>q;
vector<int> v;
int parent[50001];
void bfs(){
	visited[1] = 1;
    q.push(1);
    while(q.size()) {
    	int curr = q.front(); q.pop();
        for(int a : v[curr]){
        	if(!visited[a]){
            	parent[a] = curr;//방문하지 않은 노드를 처음에 방문했다면 curr은 a의 부모이다. 
                visited[a] = visited[curr] + 1; // depth와 방문 여부를 동시에 표시할 수 있는 배열
            }
        }
    }
}

3. 최소 공통 조상 판별

최소 공통 조상을 판별하려면 일단 더 깊은 depth에 존재하는 노드를 판별해야한다. 이 때 depth는 bfs함수를 통해 visited배열에 기록된 값에 해당하겠다. 그러면 더 큰 depth를 더 작은 depth까지 올려 depth를 맞춰준 후 (parent배열에 기록해둔 parent를 통해 따라 올라간다.) 두 노드를 번갈아가며 1칸씩 올린 후 같은 노드인지 비교하면 된다. 

queue <int>q;
vector<int> v;
int parent[50001];
void bfs(int x, int y){
	visited[1] = 1;
    q.push(1);
    while(q.size()) {
    	int curr = q.front(); q.pop();
        for(int a : v[curr]){
        	if(!visited[a]){
            	parent[a] = curr;//방문하지 않은 노드를 처음에 방문했다면 curr은 a의 부모이다. 
                visited[a] = visited[curr] + 1; // depth와 방문 여부를 동시에 표시할 수 있는 배열
            }
        }
    }
    
    int hx = visited[x];
    int hy = visited[y];
    
    if(hx >= hy) {
    	while(hx != hy) {
        	x = parent[x];
            hx--;
        }
        while(x != y) {
        	x = parent[x];
            y = parent[y];
        }
        printf("%d\n", x);
    }else {
    	while (hx != hy) {
        	y = parent[y];
            hy--;
        }
        while(x != y) {
        	x = parent[x];
            y = parent[y];
        }
        printf("%d\n", x);
    }
}

 

4. 전체 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> v[50000];
int parent[50001];
int visited[50000 + 2];
void sol(int x, int y) {
	queue<int> q;
	visited[1] = 1;
	q.push(1);
	while (q.size()) {
		int curr = q.front(); q.pop();
		for (int a : v[curr]) {
			if (!visited[a]) {
				visited[a] = visited[curr] + 1;
				parent[a] = curr;
				q.push(a);
			}
		}
	}
	int hx = visited[x];
	int hy = visited[y];
	if (hx >= hy) {
		while (hx != hy) {
			x = parent[x];
			hx--;
		}
		while (x != y) {
			x = parent[x];
			y = parent[y];
		}
		printf("%d\n", x);
	}
	else {
		while (hx != hy) {
			y = parent[y];
			hy--;
		}
		while (x != y) {
			x = parent[x];
			y = parent[y];
		}
		printf("%d\n", x);
	}
}
void input() {
	int N, M; // 노드의 N개 노드의 쌍 M
	scanf("%d", &N);
	for (int i = 0; i < N-1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		//if (a > b) swap(a, b);
		v[a].push_back(b); // b는 a에 연결되어 있다. 
		v[b].push_back(a);// b도 a에 연결되어 있다. 
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		sol(x, y);
	}
}
int main() {
	input();
	return 0;
}