[BOJ] 33851 DAG LCA

문제 요약

문제 링크: 백준 33851 - DAG LCA

문제 설명

---

접근 방법

• 모든 정점 간의 최단 거리를 계산해두고 쿼리를 간편하게 찾을 수 있도록 해야 한다.
• 공통 조상 k에 대해 k에서 u까지의 최단 경로 길이와 k에서 v까지의 최단 경로 길이 중 더 큰 값(max(dist(k, u), dist(k, v)))을 계산한다. 이 값들 중에서 가장 작은 값이 결국 쿼리의 정답이 된다. 공통 조상이 하나도 없다면 -1을 출력한다.

---

코드

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int n, m, p;
int dis[2001][2001];
vector<int>mat[2001];

void solve() {
    // 1. 모든 정점에서 다른 모든 정점으로의 최단 거리 계산 (N번의 BFS)
    for (int i = 1; i <= n; i++) {
        queue<pair<int, int>>q;
        q.push({ i,0 }); // 시작점 i, 거리 0
        while (q.size()) {
            int cur_node = q.front().first;
            int cur_dist = q.front().second;
            q.pop();

            for (int next_node : mat[cur_node]) {
                if (dis[i][next_node] > cur_dist + 1) {
                    dis[i][next_node] = cur_dist + 1;
                    q.push({ next_node, cur_dist + 1 });
                }
            }
        }
    }

    // 2. 쿼리 처리
    for (int i = 0; i < p; i++) {
        int u, v;
        cin >> u >> v;
        int ans = INF;

        // 모든 정점 j를 공통 조상 후보로 탐색
        for (int j = 1; j <= n; j++) {
            // j에서 u와 v로 가는 경로가 모두 있어야 함
            if (dis[j][u] == INF || dis[j][v] == INF)
                continue;

            // 두 경로 중 더 긴 경로 길이를 계산
            int temp = max(dis[j][u], dis[j][v]);
            // 최솟값 갱신
            ans = min(ans, temp);
        }

        if (ans == INF) ans = -1; // 공통 조상이 없는 경우
        cout << ans << '\n';
    }
}

void input() {
    cin >> n >> m >> p;
    // 거리 배열 초기화
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j)
                dis[i][j] = INF;
        }
    }
    // 그래프 정보 입력 (인접 리스트)
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        mat[u].push_back(v);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

---

마무리

• BFS로 정점 간의 거리 저장
• 전체 시간 복잡도: O(n * (n+m) + p * n) ≈14,000,000