2644 촌수계산

#include <stdio.h>
#include <queue>
#include <utility>
 
using namespace std;
 
int par[105] = { 0 };
int depth[105] = { 0 };
int man;
 
void depthSearch(int root) {
    queue<pair<int, int>> q;
    int deep = 1;
    
    q.push(make_pair(deep, root));
 
    while (!q.empty()) {        
        int idx = q.front().second;
        deep = q.front().first;
 
        if (idx == 0)
            break;
 
        depth[idx] = deep;
        q.pop();
 
        for (int i = 1; i <= man; i++) {
            if (par[i] == idx) {
                q.push(make_pair(deep + 1, i));
            }
        }
        
    }
}
 
int main() {
    scanf("%d", &man);
 
    int a,b;
    scanf("%d %d", &a, &b);
 
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        int c,d;
        scanf("%d %d", &c, &d);
 
        par[d] = c;
    }
 
    //루트 찾기 + 각 노드들의 깊이 갱신
    for (int i = 1; i <= man; i++) 
        if (par[i] == 0) 
            depthSearch(i);    
        
    //높이 맞추기
    int len = 0;
    int dpA = depth[a];
    int dpB = depth[b];
    if (dpB > dpA) {
        len = dpB - dpA;
        for(int i=0;i<len;i++) {
            b = par[b];
        }
    }
    else if (dpB < dpA) {
        len = dpA - dpB;
        for(int i=0;i<len;i++) {
            a = par[a];
        }
    }
 
    //다른 조상을 가지고 있을 경우
    int topParA = a, topParB = b;
    while (1) {
        if (par[topParA] == 0)
            break;
         topParA= par[topParA];            
    }
    while (1) {
        if (par[topParB] == 0)
            break;
        topParB = par[topParB];
    }
    if (topParB != topParA) {
        printf("-1");
        return 0;
    }
 
    //최소 공통조상 찾기
    while (a != b) {
        len+=2;
        a = par[a];
        b = par[b];
    }
 
    printf("%d", len);
}

1. BFS 를 이용해서, 각 노드들의 깊이를 체크한다

2. 높이를 맞춰준다

3. 서로 다른 조상을 가진 경우는 제외해준다

4. 같은 부모를 만날때까지 거슬러 올라간다