백준 11437 LCA java
문제 소개 www.acmicpc.net/problem/11437
내용
N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
입력
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.
출력
M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.
해결 방법
아이디어
1. dfs를 통해서 각 노드의 depths와 자기 자신의 parent를 각각 depths[]와 parents[][0] 저장한다.
2. parents[][] 배열을 통해서 각각 노드의 2의 배수의 조상을 저장한다.
3. 구하고자 하는 a, b의depth를 마춰춘다.
4. a와 b가 같은지 체크
5. 같지 않다면 parents[][] 배열을 통해서 가장 높은 2의 배수의 조상이 같은지 확인하며 다르면 a,b를 해당 조상으로 업데이트 후 반복한다.
6. 이후 그렇게 업데이트된 a혹은 b의 직속 부모인 parents[a][0], parents[b][0] 둘중 하나를 리턴한다.
실제 풀이 코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<List<Integer>> adjList = new ArrayList();
for (int i = 0; i <= n; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
String[] split = br.readLine().split(" ");
int from = Integer.parseInt(split[0]);
int to = Integer.parseInt(split[1]);
adjList.get(from).add(to);
adjList.get(to).add(from);
}
boolean[] visited = new boolean[n + 1];
int[] depths = new int[n + 1];
int[][] parents = new int[n + 1][20];
dfs(1, 0, depths, parents, adjList, visited);
setParent(n, parents);
int m = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
String[] split = br.readLine().split(" ");
int from = Integer.parseInt(split[0]);
int to = Integer.parseInt(split[1]);
sb.append(LCA(from, to, depths, parents)).append(System.lineSeparator());
}
System.out.println(sb.toString());
}
private static int LCA(int from, int to, int[] depths, int[][] parents) {
if (depths[from] > depths[to]) {
int temp = from;
from = to;
to = temp;
}
for (int n = 19; n >= 0; n--) {
if (depths[to] - depths[from] >= (1 << n)) {
to = parents[to][n];
}
}
if (from == to) return from;
for (int n = 19; n >= 0; n--) {
if (parents[from][n] != parents[to][n]) {
from = parents[from][n];
to = parents[to][n];
}
}
return parents[from][0];
}
private static void setParent(int n, int[][] parents) {
for (int j = 1; j < 20; j++) {
for (int i = 1; i <= n; i++) {
parents[i][j] = parents[parents[i][j - 1]][j - 1];
}
}
}
private static void dfs(int current, int depth, int[] depths, int[][] parents, List<List<Integer>> adjList, boolean[] visited) {
visited[current] = true;
depths[current] = depth;
for (int child : adjList.get(current)) {
if (visited[child]) continue;
parents[child][0] = current;
dfs(child, depth + 1, depths, parents, adjList, visited);
}
}
}
결과
LCA2를 먼저 풀어봐서 DP를 활용한 LCA로 해결하였다.
n이 50,000이며, m이 10,000이라서 dp를 적용하지 않고 하나씩 타고 올라가서 해결하는 방법이 O(nm)으로 아슬아슬하게 LCA에서는 통과하는가보다.
그래도 더 빠른 알고리즘을 알고있는데 굳이 느린방법을 연습할 필요는 없다고 생각하여 O(mlogn)시간복잡도인 DP+LCA 방법으로 연습하였다.
'알고리즘 문제 > 백준' 카테고리의 다른 글
프로그래머스 메뉴 리뉴얼 java (0) | 2021.02.05 |
---|---|
프로그래머스 신규 아이디 추천 java (0) | 2021.02.05 |
백준 10942 펠린드롬? java (0) | 2021.02.03 |
백준 10775 공항 java (0) | 2021.02.01 |
백준 9466 텀 프로젝트 java (0) | 2021.01.27 |