[백준 2644][C++] 촌수계산

일단 풀고 나서 다른 사람들의 풀이를 보니... 내가 굉장히 이상하게 풀었다.

사람들의 수 n이 1<=n<=100 이므로, 시간 복잡도가 높은 풀이도 상관 없을것이라 생각해서,

1. 찾는 사람 두 명이 공통으로 갖는 제일 높은 부모를 찾음

2. 부모를 찾는 과정에서 거치는 노드를 각각의 벡터에 추가

3. 두 벡터를 단순 비교하며 가장 먼저 나오는 공통 노드를 찾고 인덱스를 계산

하면 두 사람의 촌수가 나온다. 3번 과정에서 N^2 짜리 계산을 해야 하지만, n이 작으니까 괜찮겠다 싶어서 바로 코딩을 했다.

 

정석적인 풀이라고 하면

1. 먼저 그래프를 양방향으로 초기화한다.

2. 찾는 사람 한명의 노드를 큐에 넣고, 그 노드에 인접한 노드들을 큐에 넣는다

3. 걸린 촌수를 계산하는 배열(혹은 벡터)를 두고 계속해서 업데이트 시켜준다. 2~3을 반복

 

좀 이상하게 풀긴 했지만 풀이가 생각 안나면 이런식으로도 풀 수 있다는 점 ^^ ~

 

 

 

#include <iostream>
#include <string.h>
#include <vector>
 
using namespace std;
int graph[101];
void findHead(int curInd, vector<int>* v) {
    while (graph[curInd] != -1) {
        v->push_back(curInd);
        curInd = graph[curInd];
    }
    v->push_back(curInd);
}
int main() {
    memset(graph, -1, sizeof(graph));
    int N;
    int p1, p2;
    int M;
    cin >> N >> p1 >> p2 >> M;
    for (int i = 0; i < M; i++) {
        int to, from;
        cin >> to >> from;
        graph[from] = to;
    }
    vector<int> v1;
    vector<int> v2;
    findHead(p1, &v1);
    findHead(p2, &v2);
    for (int i = 0; i < v1.size(); i++) {
        for (int j = 0; j < v2.size(); j++) {
            if (v1[i] == v2[j]) {
                cout << i + j<< endl;
                return 0;
            }
        }
    }
    cout << -1 << endl;
    return 0;
 
}