[SWEA 1248 : JAVA] 공통조상

1. 문제

---

SWEA_1248_공통조상

2. 풀이

---

이 문제는 두 가지를 요구합니다.

1. 이진트리를 구성할 수 있는가?
2. 임의의 두 정점에 대해 최소 공통조상을 구할 수 있는가?

아시다시피 이진트리의 부모노드 인덱스가 N일 때, 왼쪽 자식 인덱스는 2*N이고 오른쪽 자식 인덱스는 2*N+1입니다. 
이 특성을 이용해 배열로 이진트리를 많이 구성을 하는데, 이 문제는 입력으로 들어오는 간선의 순서가 무작위인데다가 부모 정점이 자식 정점보다 항상 번호가 작은 것은 아니라는 조건까지 걸려 있습니다. (입력이 이렇게 들어오는게 조금 더 현실적인 거 같긴 합니다.. 😅 )

 

따라서, 연결 리스트 형태로 작성해야 합니다.

저는 아래와 같이 부모, 자식 번호를 담을 변수를 둔 Node라는 클래스를 두었습니다.

class Node {
    int parentIdx, leftChildIdx, rightChildIdx;
}

그리고 입력으로 들어오는 정보들에 대해 다음과 같이 세팅을 해주었습니다.

for (int i = 0; i < E; i++) {
    int parent = Integer.parseInt(st.nextToken());
    int child = Integer.parseInt(st.nextToken());
    if (nodes[parent].leftChildIdx == 0) nodes[parent].leftChildIdx = child;
    else nodes[parent].rightChildIdx = child
    nodes[child].parentIdx = parent;
}

두 번째로 공통 조상을 구하는 부분입니다.
문제에서 root 번호는 무조건 1이라고 명시해주었기 때문에 저희는 이를 토대로 선택된 두 정점에 대해 부모노드를 구해낼 수 있습니다.

// a 정점의 부모노드를 구해내는 코드입니다.
while (a != 1) {
    a = nodes[a].parentIdx;
}

root 노드를 만날 때까지 부모노드를 계속 거슬러 올라가는 코드입니다.
이 코드를 응용하면 a와 b 정점간의 공통 조상을 찾을 수 있습니다.
위 코드로 a정점에 대해 root 노드까지 부모노드를 계속 거슬러 올라가면서 마킹을 해주는 겁니다. (visited 변수를 두는 등)
그리고 b정점에 대해 마찬가지로 부모노드를 계속 찾아가는데 이때, 마킹이 된 노드가 있다면 그것은 a정점의 부모노드였다는 의미이므로 둘 의 최소 공통 조상노드가 됩니다. 

3. 코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static int T;
    private static int V, E, a, b;
    private static int size;
    private static Node[] nodes;
    private static boolean[] visited;
    private static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(in.readLine());
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            nodes = new Node[V + 1];
            visited = new boolean[V + 1];
            for (int i = 1; i <= V; i++) {
                nodes[i] = new Node(i);
            }

            // 트리 생성
            st = new StringTokenizer(in.readLine());
            for (int i = 0; i < E; i++) {
                int parent = Integer.parseInt(st.nextToken());
                int child = Integer.parseInt(st.nextToken());
                if (nodes[parent].leftChildIdx == 0) nodes[parent].leftChildIdx = child;
                else nodes[parent].rightChildIdx = child;
                nodes[child].parentIdx = parent;
            }

            // 공통 조상 찾기
            // 공통 조상을 찾고자 하는 두 노드에 대해 각각 부모 노드를 찾아가며 마킹한다.
            // 이때 하나의 노드가 이미 마킹된 부모노드를 만났다면 그게 공통 조상인 것.
            int commonParent = 1;
            while (true) {
                if (a != 1) {
                    int parent = nodes[a].parentIdx;
                    if (visited[parent]) {
                        commonParent = parent;
                        break;
                    }
                    visited[parent] = true;
                    a = parent;
                }
                if (b != 1) {
                    int parent = nodes[b].parentIdx;
                    if (visited[parent]) { // 부모노드가 이미 마킹되어 있다면 이게 최소 공통 조상노드이다.
                        commonParent = parent;
                        break;
                    }
                    visited[parent] = true;
                    b = parent;
                }
            }
            size = 0;
            get(nodes[commonParent]);
            sb.append("#").append(tc).append(" ").append(commonParent).append(" ").append(size).append("\n");
        }
        System.out.println(sb);
    }

    static void get(Node node) {
        size++;
        if (node.leftChildIdx != 0) get(nodes[node.leftChildIdx]);
        if (node.rightChildIdx != 0) get(nodes[node.rightChildIdx]);
    }

    private static class Node {
        int data;
        int parentIdx, leftChildIdx, rightChildIdx;

        Node(int data) {
            this.data = data;
            this.parentIdx = 0;
            this.leftChildIdx = 0;
            this.rightChildIdx = 0;
        }
    }

}