백준 3176 (도로 네트워크) - LCA 풀이(Sparse Table 사용)

문제

---

N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 

모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.

총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.

 

 

 

 

 

풀이

---

 

LCA 문제에서 SparseTable 에 2^i  의 조상까지의 경로에 최소와 최대를 저장할 배열을 두개 더 선언한다.

 

pmax[][] : 2 ^ i 까지의 조상으로 가는 경로에 최댓값을 저장

pmin[][] : 2 ^ i 까지의 조상으로 가는 경로에 최솟값을 저장

 

이 두가지의 배열을 이용하면 값을 구할 수 있다.

 

LCA 코드를 보겠다.

public static node LCA(int a, int b, int k) {
   	if(depth[a] < depth[b]) {
   		int temp = a;
   		a = b;
   		b = temp;
   	}
   	
   	int max = Integer.MIN_VALUE;
   	int min = Integer.MAX_VALUE;
    	
   	for(int i = k - 1 ; i >= 0 ; i--) {
   		if(Math.pow(2, i) <= depth[a] - depth[b]) {
   			
   			max = Math.max(max, pmax[a][i]);
   			min = Math.min(min, pmin[a][i]);
  			
   			a = parents[a][i];
   		}
   	}
   	
   	if(a == b)
  		return new node(min, max);
   	
   	for(int i = k - 1 ; i >= 0 ; i--) {
   		if(parents[a][i] != parents[b][i]) {
   			
  			max = Math.max(max, Math.max(pmax[a][i], pmax[b][i]));
   			min = Math.min(min, Math.min(pmin[a][i], pmin[b][i]));
   			
   			a = parents[a][i];
   			b = parents[b][i];
   		}
   	}
   	
   	max = Math.max(max, Math.max(pmax[a][0], pmax[b][0]));
   	min = Math.min(min, Math.min(pmin[a][0], pmin[b][0]));
   	
   	return new node(min, max);
}

 

값을 바꿔줄때 마다 max 값과 min 값을 최신화 시켜준다.

 

마지막으로 최소공통조상의 값으로 max, min을 최신화 시켜준다.

 

 

<전체 코드>

import java.io.*;
import java.util.*;


public class Main {
	
	static class node{
		
		public int num, dist;
		
		public node(int num, int dist) {
			
			this.num = num;
			this.dist = dist;
		}
	}

	static StringBuilder sb = new StringBuilder();
	static int[] depth;
	static int[][] parents;
	static int[][] pmax;
	static int[][] pmin;
	static List<node>[] tree;
	
	
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(bufferedReader.readLine());
        
        tree = new List[n + 1];
        
        for(int i = 0 ; i <= n ; i++) {
        	tree[i] = new LinkedList<node>();
        }
        
        for(int i = 0 ; i < n - 1; i++) {
        	StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        	
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	int dist = Integer.parseInt(st.nextToken());
        	
        	tree[a].add(new node(b, dist));
        	tree[b].add(new node(a, dist));
        }
        
        int tmp = 1;
        int K = 0;
        while(tmp <= n) {
        	tmp <<= 1;
        	K++;
        }
        
        depth = new int[n + 1];
        parents = new int[n + 1][K];
        pmax = new int[n + 1][K];
        pmin = new int[n + 1][K];
        
        DFS(1, 1);
        DP_Algorithm(K, n);
        
        int m = Integer.parseInt(bufferedReader.readLine());
        
        for(int i = 0 ; i < m ; i++) {
        	StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        	
        	int a = Integer.parseInt(st.nextToken());
        	int b = Integer.parseInt(st.nextToken());
        	
        	node result = LCA(a, b, K);
        	sb.append(result.num + " " + result.dist + "\n");
        	
        }
        
        System.out.println(sb);
    }
    
    public static void DFS(int node, int cnt) {
    	depth[node] = cnt;
    	
    	for(node next : tree[node]) {
    		if(depth[next.num] == 0) {
    			parents[next.num][0] = node;
    			pmax[next.num][0] = next.dist;
    			pmin[next.num][0] = next.dist;
    			DFS(next.num, cnt + 1);    			
    		}
    	}
    }
    
    public static void DP_Algorithm(int k, int n) {
    	for(int i = 1; i < k ; i++) {
    		for(int j = 1; j <= n ; j++) {
    			parents[j][i] = parents[parents[j][i - 1]][i - 1];
    			pmax[j][i] = Math.max(pmax[j][i-1], pmax[parents[j][i-1]][i-1]);
    			pmin[j][i] = Math.min(pmin[j][i-1], pmin[parents[j][i-1]][i-1]);
    		}
    	}
    }
    
    public static node LCA(int a, int b, int k) {
    	if(depth[a] < depth[b]) {
    		int temp = a;
    		a = b;
    		b = temp;
    	}
    	
    	int max = Integer.MIN_VALUE;
    	int min = Integer.MAX_VALUE;
    	
    	for(int i = k - 1 ; i >= 0 ; i--) {
    		if(Math.pow(2, i) <= depth[a] - depth[b]) {
    			
    			max = Math.max(max, pmax[a][i]);
    			min = Math.min(min, pmin[a][i]);
    			
    			a = parents[a][i];
    		}
    	}
    	
    	if(a == b)
    		return new node(min, max);
    	
    	for(int i = k - 1 ; i >= 0 ; i--) {
    		if(parents[a][i] != parents[b][i]) {
    			
    			max = Math.max(max, Math.max(pmax[a][i], pmax[b][i]));
    			min = Math.min(min, Math.min(pmin[a][i], pmin[b][i]));
    			
    			a = parents[a][i];
    			b = parents[b][i];
    		}
    	}
    	
    	max = Math.max(max, Math.max(pmax[a][0], pmax[b][0]));
    	min = Math.min(min, Math.min(pmin[a][0], pmin[b][0]));
    	
    	return new node(min, max);
    }
}