백준 2644 - 촌수계산

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

// 백준 2644 - 촌수계산
// https://www.acmicpc.net/problem/2644

// 문제 설명
// 부모-자식 관계(1촌)가 주어질 때 두 사람의 촌수를 구하라
// 연결되지 않으면 -1 출력

// 접근
// - 양방향 인접 리스트 구성
// - s에서 DFS, e 도달 시 depth를 ret에 저장 후 true 반환(조기 종료)

#include <iostream>
#include <vector>
using namespace std;
#define endl '\n'

int n, m;
int s, e;
vector<int> v[104];
bool visited[104];

bool dfs(int here, int depth, int& ret)
{
    visited[here] = true;
    if (here == e)
    {
        ret = depth;
        return true;
    }
    for (int i : v[here])
        if (!visited[i])
            if (dfs(i, depth + 1, ret))
                return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s >> e >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int ret = -1;
    dfs(s, 0, ret);
    cout << ret << endl;
    return 0;
}

정리

• bool dfs(int here, int depth, int& ret) — 목표 도달 여부를 bool로 반환하고 깊이는 int& 참조로 전달한다. 목표를 찾으면 true가 위로 전파되어 불필요한 탐색을 즉시 중단한다.
• ret = -1로 초기화 — s와 e가 연결되지 않으면 DFS가 false를 반환하고 ret은 그대로 -1이 된다.
• 부모-자식 관계는 양방향 탐색이 필요하다 — 촌수를 올라가거나 내려가며 찾아야 하므로 v[a] ↔ v[b] 모두 push.

핵심 요약 — 촌수는 결국 그래프에서 두 노드 사이의 거리다. bool 반환 + int& 참조 조합이면 목표에 닿는 순간 true가 위로 전파되며 탐색이 끊기고, 연결되지 않은 경우는 초기값 -1이 그대로 답이 된다.