2644번: 촌수계산

[yeonddori]

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

문제 설명

두 사람 간의 촌수를 계산하는 문제이며, 촌수는 두 사람 사이를 연결하는 최소 관계의 수를 의미합니다. 주어진 그래프는 무방향 그래프이므로 노드 간의 최단 경로를 계산하는 방식으로 문제를 해결할 수 있습니다.

문제 풀이

최단 거리를 찾기 위해서는 DFS보다는 최단 거리 탐색에 최적화된 BFS를 사용하는 것이 적합합니다.
무방향 그래프를 인접 리스트로 구성한 뒤, 시작 노드에서 BFS를 수행하며 방문한 노드를 기록하고 각 노드까지의 거리를 계산합니다.
도착 노드까지의 거리를 반환하며, 만약 도달할 수 없는 경우에는 -1을 반환합니다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, a, b;
vector<vector<int>> adj;

int bfs() {
    vector<int> cnt(n + 1, -1);
    queue<int> q;
    q.push(a);
    cnt[a] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : adj[x]) {
            if (cnt[y] == -1) {
                cnt[y] = cnt[x] + 1;
                q.push(y);
            }
        }
    }
    return cnt[b];
}

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

    int m;
    cin >> n >> a >> b >> m;
    adj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    cout << bfs();
    return 0;
}

후기

청년 치매가 도래한 것인지 또다시 BFS를 풀려고 하니 머리가 안 돌아가더군요.. 코드가 마음에 들진 않지만 그래도 전보단 빨리 푼 것 같습니다.