백준 33851: DAG LCA

문제 요약

무가중치 방향 비순환 그래프
$G$가 주어진다. 다음 쿼리를 수행하는 프로그램을 작성하시오.

•  $u$ $v$: 두 정점 $u$와 $v$로 가는 경로가 모두 존재하는 모든 정점에 대해 $u$와 $v$로 가는 두 최단 경로의 길이 중 작지 않은 값의 최솟값을 출력한다. 두 정점 $u$와 $v$로 가는 경로가 존재하는 정점이 없다면 대신 -1을 출력한다.

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS

문제 풀이

방향 비순환 그래프에서 LCA를 찾는 문제이다. 이는 일종의 dp를 이용해서 구할 수 있는데, 어떤 정점으로부터 서로다른 두 정점 v, u의 거리를 미리 저장하는 것이다. 이렇게 하면 들어오는 쿼리에 대해 모든 정점을 탐색하며 어떤 정점으로부터 v까지의 거리와 u까지의 거리 중 최댓값을 최소로 하는 정답을 찾을 수 있다.

풀이 코드

import java.util.*;
import java.io.*;
 
class Main
{
	static int n, m, q, res, a, b;
	static List<Integer>[] e;
	static int[][] dp;
	
	public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());
        int u, v;
        e = new List[n];
    	dp = new int[n][n];
        Queue<Integer> qq = new ArrayDeque<>();
        for(int i = 0; i < n; i++)
        	e[i] = new ArrayList<>();
        
        for(int i = 0; i < m; i++) {
        	st = new StringTokenizer(br.readLine());
        	u = Integer.parseInt(st.nextToken()) - 1;
        	v = Integer.parseInt(st.nextToken()) - 1;
        	e[v].add(u);
        }
    	for(int i = 0; i < n; i++)
    		Arrays.fill(dp[i], -1);
        for(int i = 0; i < n; i++) {
    		dp[i][i] = 0;
    		qq.offer(i);
    		while(!qq.isEmpty()) {
    			int t = qq.poll();
    			for(int it : e[t]) {
    				if(dp[i][it] < 0) {
    					dp[i][it] = dp[i][t] + 1;
    					qq.offer(it);
    				}
    			}
        	}
    	}
        for(int k = 0; k < q; k++) {
        	st = new StringTokenizer(br.readLine());
        	a = Integer.parseInt(st.nextToken()) - 1;
        	b = Integer.parseInt(st.nextToken()) - 1;
        	res = -1;
        	for(int i = 0; i < n; i++) {
        		if(dp[a][i] >= 0 && dp[b][i] >= 0) {
        			if(res < 0) res = Math.max(dp[a][i], dp[b][i]);
        			res = Math.min(res, Math.max(dp[a][i], dp[b][i]));
        		}
        	}
        	sb.append(res).append("\n");
        }
        System.out.println(sb);
    }
}