[백준] 3176번 : 도로 네트워크

문제

www.acmicpc.net/problem/3176 

3176번: 도로 네트워크

문제해결방법

이 문제는 최소 공통 조상(LCA)를 찾아서 푸는 문제였다.

2^i 번째 조상을 저장하는 배열로 만들면서 동일한 방법으로 2^i 까지의 경로에 있는 도로의 길이의 최대, 최소값을 저장하는 배열을 만든다.

두 도시가 주어지면 LCA를 찾으러 올라가면서 도로의 길이의 최대, 최소값을 찾으면서 올라간다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
 
 
public class Main3176_도로네트워크 {
    
    public static int N, K;
    public static int[] depth;
    public static int[][] parent, maxValue, minValue;
    public static List<int[]>[] edge;
    
    public static void bfs(int root) {
        int d = 0;
        boolean[] v = new boolean[N+1];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(root);
        v[root] = true;
        depth[root] = d++;
        maxValue[0][root] = Integer.MIN_VALUE;
        minValue[0][root] = Integer.MAX_VALUE;
        while(!q.isEmpty()) {
            int size = q.size();
            for(int s=0; s<size; s++) {
                int cur = q.poll();
                for(int[] e : edge[cur]) {
                    if(!v[e[0]]) {
                        v[e[0]] = true;
                        depth[e[0]] = d;
                        parent[0][e[0]] = cur;
                        maxValue[0][e[0]] = e[1];
                        minValue[0][e[0]] = e[1];
                        q.add(e[0]);
                    }
                }
            }
            d++;
        }
    }
    
    public static void makeParent() {
        for(int i=1; i<=20; i++) {
            for(int k=1; k<=N; k++) {
                parent[i][k] = parent[i-1][parent[i-1][k]];
                if(parent[i-1][parent[i-1][k]]==0) continue;
                maxValue[i][k] = Math.max(maxValue[i-1][k], maxValue[i-1][parent[i-1][k]]);
                minValue[i][k] = Math.min(minValue[i-1][k], minValue[i-1][parent[i-1][k]]);
            }
        }
    }
    
    public static int[] lca(int l, int r) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        if(depth[l]>depth[r]) {
            int temp = l;
            l = r;
            r = temp;
        }
        for(int i=20; i>=0; i--) {
            if(depth[r]-depth[l] >= (1<<i)) {
                max = Math.max(max, maxValue[i][r]);
                min = Math.min(min, minValue[i][r]);
                r = parent[i][r];
            }
        }
        if(r==l) return new int[] {min, max};
        for(int i=20; i>=0; i--) {
            if(parent[i][l]!=parent[i][r]) {
                max = Math.max(max, maxValue[i][l]);
                max = Math.max(max, maxValue[i][r]);
                min = Math.min(min, minValue[i][l]);
                min = Math.min(min, minValue[i][r]);
                l = parent[i][l];
                r = parent[i][r];
            }
        }
        max = Math.max(max, maxValue[0][l]);
        max = Math.max(max, maxValue[0][r]);
        min = Math.min(min, minValue[0][l]);
        min = Math.min(min, minValue[0][r]);
        return new int[] {min, max};
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        depth = new int[N+1];
        parent = new int[21][N+1];
        maxValue = new int[21][N+1];
        minValue = new int[21][N+1];
        edge = new List[N+1];
        for(int i=1; i<=N; i++) edge[i] = new ArrayList<>();
        for(int i=1; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edge[a].add(new int[] {b, c});
            edge[b].add(new int[] {a, c});
        }
        bfs(1);
        makeParent();
        int K = Integer.parseInt(br.readLine());
        for(int i=0; i<K; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            int[] result = lca(l, r);
            System.out.println(result[0]+" "+result[1]);
        }
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.