[백준] 11437번 - LCA (java)

[백준] 11437번 - LCA (java)

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 3 초 256 MB 12641 5564 3271 43.006%

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

풀이

제한시간이 3초면 java기준 3*2 +1인 7초내에 해결하면 되므로 O(NM)의 시간복잡도로도 해결할 수 있다.

하지만 LCA 알고리즘을 공부 해 보고자 LCA알고리즘으로 풀어보았다.

입력은 순서가 없는 그래프로 주어지며 루트노드는 무조건 1이므로 그래프를 탐색하는 과정이 필요하다.

LCA 알고리즘

DFS를 수행하며 각 노드의 DEPTH와 그 노드의 부모를 저장한다. (완전탐색) 찾고자 하는 두 노드의 Depth가 같을 때 까지 부모를 찾는다. 같은 Depth에서의 정점이 같지 않다면 둘 모두의 부모를 비교하고 같을 때 까지 수행한다. 무조건 root에서 정점이 같기 때문에 3번의 과정을 계속 반복한다면 정답을 찾을 수 있다.

과정

DFS

static void dfs(int v, int d) { visited[v] = true; depth[v] = d; for (Node temp = graph[v]; temp != null; temp = temp.link) { if (!visited[temp.vertex]) { parent[temp.vertex] = v; // 부모 정점을 저장. dfs(temp.vertex, d + 1); // DFS 마저 탐색 } } }

LCA

static int lca(int a, int b) { while (depth[a] != depth[b]) { // depth가 같지 않다면 if (depth[a] > depth[b]) // 더 큰 depth의 부모를 찾아 올라간다. a = parent[a]; else b = parent[b]; } while (a != b) { // depth가 같다면 공통 조상을 찾을 때 까지 부모를 찾아 올라간다. a = parent[a]; b = parent[b]; } return a; }

최종 소스코드

import java.io.*; import java.util.*; public class BJ_G3_11437_LCA { static int N, M; static int[] parent; static int[] depth; static boolean[] visited; static Node[] graph; static StringTokenizer st; static class Node { int vertex; Node link; public Node(int vertex, Node link) { super(); this.vertex = vertex; this.link = link; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); N = Integer.parseInt(br.readLine()); parent = new int[N + 1]; depth = new int[N + 1]; visited = new boolean[N + 1]; graph = new Node[N + 1]; for (int i = 1; i < N; i++) { st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); graph[start] = new Node(end, graph[start]); graph[end] = new Node(start, graph[end]); } dfs(1, 0); M = Integer.parseInt(br.readLine()); for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); sb.append(lca(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()))); sb.append("

"); } System.out.println(sb.toString()); } static void dfs(int v, int d) { visited[v] = true; depth[v] = d; for (Node temp = graph[v]; temp != null; temp = temp.link) { if (!visited[temp.vertex]) { parent[temp.vertex] = v; dfs(temp.vertex, d + 1); } } } static int lca(int a, int b) { while (depth[a] != depth[b]) { if (depth[a] > depth[b]) a = parent[a]; else b = parent[b]; } while (a != b) { a = parent[a]; b = parent[b]; } return a; } }

from http://skdltm117.tistory.com/52 by ccl(A) rewrite - 2021-12-26 15:01:41