[java]공통조상 - SWEA 1248

풀이

문제 해석을 하자면,

• 두개의 정점이 주어지면 이것의 공통조상을 구하고, 해당 서브트리의 크기를 도출하라.
  • 정점의 번호는 1부터 V까지의 정수이며, 루트 정점은 항상 1번이다.
  • 간선은 항상 “부모 자식” 순서이다.

풀이

• 트리를 잘 알고있다면 생각보다 쉬운 문제이다.
  • 이진트리라서 E가 별로 크지않다. 이는 희소행렬로 볼 수 있고, 연결리스트를 사용하는게 좋다.
• 2개 함수 구현하자
  • 부모 찾기
    • 따로 visited 배열을 만들어서 방문할때마다 ++를 했고,
    • 2회 방문했을시 공통조상으로 구했다.
  • BFS or DFS 로 서브트리 크기 구하기 -> 자기자신(+1) 포함
    • 간단해서 생략

코드

public static int result;

public static void dfs(int root, List<Integer>[] inArr) {
    //base condition
    List<Integer> list = inArr[root];
    if(list.isEmpty()) return;
	//recursion
    for(int num : list) {
        result++;
        dfs(num, inArr);
    }
}

public static int findAncestor(int[] pChkArr, int first, int second, int V) {
    int answer = 0;
    int[] visited = new int[V+1]; // 매번 새로 할당 (0)
    visited[first]++;
    visited[second]++;

    while(true) {
        // 종료시점
        if(visited[first] == 2) {
            answer = first;
            break;
        } else if(visited[second] == 2) {
            answer = second;
            break;
        }
        // 1 은 root 입니다.
        if(first != 1) {
            first = pChkArr[first];
            visited[first]++;
        }
        if(second != 1) {
            second = pChkArr[second];
            visited[second]++;
        }
    }

    return answer;
}

public static void main(String args[]) throws Exception
{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    int T = Integer.parseInt(br.readLine());
    for(int t = 1; t <= T; t++)
    {
        //input
        StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
        int V = Integer.parseInt(stk.nextToken());
        int E = Integer.parseInt(stk.nextToken());
        int first = Integer.parseInt(stk.nextToken());
        int second = Integer.parseInt(stk.nextToken());
        stk = new StringTokenizer(br.readLine(), " ");
        List<Integer>[] inArr = new ArrayList[V+1]; // 매번 새로할당
        for(int i=0; i<V+1; i++) inArr[i] = new ArrayList<>();
        int[] pChkArr = new int[V+1];
        result = 1; //init
        for(int i=0; i<E; i++) {
            int parent = Integer.parseInt(stk.nextToken());
            int child = Integer.parseInt(stk.nextToken());
            inArr[parent].add(child); // 양방향 X
            pChkArr[child] = parent; // 부모 기록
        }
        //run
        // 1. 조상 부모 구하기
        int ancestor = findAncestor(pChkArr, first, second, V);
        // 2. 서브트리 크기 구하기
        dfs(ancestor, inArr);
        sb.append("#").append(t).append(" ").append(ancestor).append(" ").append(result).append("\n");
    }
    //ouput
    System.out.print(sb);
}

느낀점

생략