[백준] 2644번 촌수 계산

문제 링크

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

 

내 코드가 대단히 메모리를 적게 먹거나 코드 길이가 짧은 편에 속하지는 않는다. 그동안 제출된 현황의 코드를 보니까 메모리와 코드 길이 기준으로 대충 상위 30%에는 속한다. 가독성은 더 좋다고 생각한다. 내가 작성해서가 아니라 그냥 평범한 로직이라서 그렇다.

 

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

int N, M;
int p1, p2;

vector<int> parents;
bool visited[101];
queue<pair<int, int>> q;

int main()
{
    cin >> N;
    cin >> p1 >> p2;
    cin >> M;

    parents.resize(N + 1);

    for (int i = 0; i < M; ++i)
    {
        int parent, child;
        cin >> parent >> child;

        parents[child] = parent;
    }

    q.push({ p1, 0 });

    while (q.empty() == false)
    {
        auto [person, degree] = q.front();
        q.pop();

        if (person == p2)
        {
            cout << degree;
            return 0;
        }        

        int parent = parents[person];
        if (parent && visited[parent] == false)
        {            
            visited[parent] = true;
            q.push({ parent, degree + 1 });
        }
        
        for (int i = 1; i <= N; ++i)
        {
            if (parents[i] == person && visited[i] == false)
            {
                visited[i] = true;
                q.push({ i, degree + 1 });
            }
        }
    }

    cout << -1;
}