[코딩테스트] SWEA 1248 공통조상(Java)

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
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)
  서브 트리의 자식 카운트 숫자를 구하는 함수
  
  • 자기 자신을 더하고 자식 수를 구합니다.