SWEA 1248. 공통조상 :: 돼지개발자

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD

"트리 구현"

트리를 구현하면된다. Complete Binary Tree 였다면 모두 배열에 넣고 좀더 쉽게 구할수 있었겠지만, 그냥 이진트리여서 그러지 못하고 트리를 구현했다. 대신 부모로 가는 경로를 쉽게 구하고자 해당 노드의 left, right 이외에 parent 변수도 함께 넣어줬다.

그렇게 한 후, A와 B의 공통 조상을 구하기 위해 A와 B의 조상을 번갈아가면서 찾으며 마킹을 했다. 이미 누군가가 지나간 노드의 경우 공통 조상이 되므로, 그 공통 조상을 구했고, 그 하위부터 다시 재귀적으로 공통 조상의 자식들을 l,r 이용해 돌아가며 구했다.

root의 경우 조상이 없으므로 예외 처리해야한다. ( A 가 root에 도달했으면, A는 더이상 탐색하지 않도록)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Solution {
    
    static int T;
    static int v,e,a,b;
    static int n;
    static Node nodes[];
    static int[] visited;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        int t = 1;
        while(T-- > 0) {
            StringTokenizer 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());
            
            nodes = new Node[v+1];
            visited = new int[v+1];
            n = 0;
            for (int i = 1; i <= v; i++) {
                nodes[i] = new Node(i);
            }
            
            st = new StringTokenizer(br.readLine());
            
            // 트리 생성
            for (int i = 0; i < e; i++) {
                int p = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                
                if(nodes[p].l == 0) {
                    nodes[p].l = c;
                }
                else {
                    nodes[p].r = c;
                }
                nodes[c].p = p;
            }
            
            // 공통 조상 찾기
            int parent = 1;
            
            while(true) {
                if(a != 1) {
                    int pa = nodes[a].p;
                    
                    if(visited[pa] == 1) {
                        parent = pa;
                        break;
                    }
                    visited[pa] = 1;
                    a = pa;
                }
                
                if( b != 1) {
                    int pb = nodes[b].p;
                    
                    if(visited[pb] == 1) {
                        parent = pb;
                        break;
                    }
                    visited[pb] = 1;    
                    b = pb;
                }
            }
            get(nodes[parent]);
            System.out.printf("#%d %d %d\n",t++,parent,n);
        }
    }
    
    static void get(Node node) {
        n++;
        if(node.l != 0) get(nodes[node.l]);
        if(node.r != 0) get(nodes[node.r]);    
    }
}
 
class Node {
    int data;
    int p;
    int l;
    int r;
    
    Node(int data) {
        this.data = data;
        this.p = 0;
        this.l = 0;
        this.r= 0;
    }
}