제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1248 공통조상입니다.
먼저 효율적인 풀이인지는 사실 잘 모르겠습니다. 제가 푼 방법만 공유드리겠습니다.
(후에 찾아보니 binary lifting 방법이 있더라구요. 추후에 공부 후 포스팅하도록 하겠습니다.)
포인트
트리의 특성을 활용한 문제입니다.
트리의 각 노드는 depth가 존재하고 같은 depth로 만들고 그 부모가 같은지 확인하고 다르다면 부모 노드로 이동하는 로직으로 구성했습니다.
소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Q1248 {
static class Node {
int parent, depth;
int childCnt = 0;
public Node(int parent, int depth) {
this.parent = parent;
this.depth = depth;
}
}
private static int testCase, V, E, a, b;
private static Node[] parents;
private static List<List<Integer>> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
testCase = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st;
for (int t = 1; t <= testCase; t++) {
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
init();
st = new StringTokenizer(br.readLine());
for (int i = 0; i < E; i++) {
int parent = Integer.parseInt(st.nextToken());
int child = Integer.parseInt(st.nextToken());
parents[child] = new Node(parent, parents[parent].depth + 1);
parents[parent].childCnt++;
list.get(parent).add(child);
}
for (int i = 1; i <= V; i++) {
if (parents[i].parent == i && !list.get(i).isEmpty()) {
setDepth(i, 0);
}
}
int grand = findCommonGrand();
int childCnt = findChildCnt(grand);
sb.append("#").append(t).append(" ").append(grand).append(" ").append(childCnt);
if (t != testCase) {
sb.append("\n");
}
}
System.out.println(sb);
}
private static int findChildCnt(int root) {
int cnt = 1;
Queue<Integer> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int parent = q.poll();
for (int child : list.get(parent)) {
cnt++;
q.add(child);
}
}
return cnt;
}
private static int findCommonGrand() {
int n1 = a;
int n2 = b;
while (n1 != n2) {
while(parents[n1].depth > parents[n2].depth) {
n1 = parents[n1].parent;
}
while (parents[n1].depth < parents[n2].depth) {
n2 = parents[n2].parent;
}
while(n1 != n2) {
n1 = parents[n1].parent;
n2 = parents[n2].parent;
}
}
return n1;
}
private static void init() {
parents = new Node[V + 1];
for (int i = 0; i <= V; i++) {
parents[i] = new Node(i, 0);
}
list = new ArrayList<>();
for (int i = 0; i <= V; i++) {
list.add(new ArrayList<>());
}
}
private static void setDepth(int curr, int depth) {
parents[curr].depth = depth;
for (int child : list.get(curr)) {
setDepth(child, depth + 1);
}
}
}
코드 설명
static class Node {
int parent, depth;
int childCnt = 0;
public Node(int parent, int depth) {
this.parent = parent;
this.depth = depth;
}
}
- Node class
현재 노드의 부모노드(parent), depth와 자식 카운트를 인스턴스 변수를 선언합니다.
private static void setDepth(int curr, int depth) {
parents[curr].depth = depth;
for (int child : list.get(curr)) {
setDepth(child, depth + 1);
}
}
- setDepth(int curr, int depth)
depth를 설정하는 함수
- curr을 기준으로 dfs 탐색하면서 depth를 설정합니다.
private static int findCommonGrand() {
int n1 = a;
int n2 = b;
while (n1 != n2) {
while(parents[n1].depth > parents[n2].depth) {
n1 = parents[n1].parent;
}
while (parents[n1].depth < parents[n2].depth) {
n2 = parents[n2].parent;
}
while(n1 != n2) {
n1 = parents[n1].parent;
n2 = parents[n2].parent;
}
}
return n1;
}
- findCommonGrand()
공통 조상을 찾는 함수
- node a와 b에 대해, depth를 일치시킨 후 그 둘의 부모가 같은지 파악합니다.
private static int findChildCnt(int root) {
int cnt = 1;
Queue<Integer> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
int parent = q.poll();
for (int child : list.get(parent)) {
cnt++;
q.add(child);
}
}
return cnt;
}
- findChildCnt(int root)
서브 트리의 자식 카운트 숫자를 구하는 함수
