[백준] 1761 정점들의 거리

www.acmicpc.net/problem/1761

1761번: 정점들의 거리

2020-12-20

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main1761 {
    public static class Node {
        int y;
        int v;
        public Node(int y, int v) {
            this.y = y;
            this.v = v;
        }
    }
 
    public static int N, M, dp[][], depth[], dist[];
    public static List<List<Node>> list;
    public static boolean vtd[];
    public static int maxlevel = 16;
    
    public static void dfs(int cur, int parent) {
        vtd[cur] = true;
        
        depth[cur] = depth[parent] + 1;
 
        for(Node next: list.get(cur)) {
            if(!vtd[next.y]) {
                vtd[next.y] = true;
                dp[next.y][0] = cur;
                dist[next.y] = dist[cur] + next.v;
//                dist[cur][next.y] = next.v;
//                dist[parent][next.y] = dist[parent][cur] + dist[cur][next.y];
                dfs(next.y, cur);
            }
        }
    }
    
    public static void solve() {
        for(int y = 1; y <= maxlevel; y++) {
            for(int x = 1; x <= N; x++) {
                dp[x][y] = dp[dp[x][y-1]][y-1];
            }
        }
    }
    
    public static int lca(int x, int y) {
        //x를 더 깊은 depth로 가정
        
        if(depth[x] < depth[y]) {
            int tmp = y;
            y = x;
            x = tmp;
        }
        
        for(int i = maxlevel; i >= 0; i--) {
            if(Math.pow(2, i) <= depth[x] - depth[y]) {
                x = dp[x][i];
            }
        }
 
        if(x == y) return x;
        else {
            for(int i = maxlevel; i >= 0; i--) {
                if(dp[x][i] != dp[y][i]) {
                    x = dp[x][i];
                    y = dp[y][i];
                }
            }
            x = dp[x][0];
        }
        return x;
    }
    
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine().trim());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        vtd = new boolean[N+1];
        dp = new int[N+1][maxlevel+1];
        depth = new int[N+1];
//        dist = new int[N+1][N+1];
        dist = new int[N+1];
        
        for(int i = 0; i <= N; i++) list.add(new ArrayList<>());
        
        for(int i = 0; i < N-1; i++) {
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list.get(x).add(new Node(y,v));
            list.get(y).add(new Node(x,v));
        }
        
        dfs(1, 0);
        solve();
        
        st = new StringTokenizer(bf.readLine().trim());
        M = Integer.parseInt(st.nextToken());
        
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int res = lca(x, y);
            System.out.println(dist[x] + dist[y] - 2*dist[res]);
        }
    }
}
 

void2017.tistory.com/134

[백준] 11437, 11438 LCA (2)

#문제풀이

1. 기존 LCA + 정점사이의 거리 계산이 필요한 문제이다. LCA 코드는 기존에 했던 방식과 동일하게 풀었다. 

 

2. 정점계산을 처음에는 위에 주석처리를 한 것처럼 2차원 배열로 계산을 하였다. dist[x][y]를 만들어서, x는 lca값 y는 찾고자 하는 정점으로 계산을 하였다. 답은 맞았지만 제출을 하면 메모리초과가 나왔다.

 

3.  다른 방법이 딱히 생각이 나지 않아서 다른 블로그들을 참조해봤다. dist를 1차원 배열로 만들고, dist[x]값은 1부터~노드x까지의 합이다. 그래서 x, y사이의 거리를 구할 때는 dist[x] + dist[y] 를 한 후 2*dist[lca(x,y)] 중복되는 값을 빼주었다. 

 

예를 들어 루트가 1이고 5,7 정점 사이의 거리를 구해야 할 때, lca(5,7)이 3인 경우가 있다고 가정해본다. 그러면 dist[5] 는 1부터 5까지의 거리이고, dist[7]은 1부터 7까지의 거리이다. 이 때, lca(5,7)의 값인 3의 정점도 2번 지나가게 된다. 그래서 dist[3] (1부터 3까지의 거리)에 2를 곱한 값을 빼주면된다.