[SWEA] 1248 공통 조상 D5 / JAVA

문제

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

SW Expert Academy

 

[입력]
가장 첫 번째 줄에 테스트케이스의 수가 주어진다.
각 케이스의 첫 번째 줄에는 정점의 개수 V(10 ≤ V ≤ 10000)와 간선의 개수 E, 공통 조상을 찾는 두 개의 정점 번호가 주어진다.
각 케이스의 두 번째 줄에는 E개 간선이 나열된다. 간선은 항상 “부모 자식” 순서로 표기된다.
위에서 예로 든 트리에서 정점 5와 8을 잇는 간선은 “5 8”로 표기된다.
정점의 번호는 1부터 V까지의 정수이며, 루트 정점은 항상 1번이다.

[출력]
각 테스트케이스마다 '#t'(t는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 가장 가까운 공통 조상의 번호와 그것을 루트로 하는 서브 트리의 크기를 공백으로 구분하여 출력하라.

입력
10
13 12 8 13
1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 10 6 11 11 13
10 9 2 10
1 2 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10

출력
#1 3 8
#2 1 10

접근 방식

트리 데이터를 Node로 만들어서 저장시킨다.

원하는 값부터 시작해서 각 Node에 저장된 parent를 찾아가며 부모 노드로 이동

해당 노드를 순서대로 리스트에 저장한다.

=> findParent 메소드로 만들어서 리스트 저장

이렇게 생성된 두 리스트를 앞에서부터 비교하면서 두 값이 달라진 곳의 부모 노드가 가장 가까운 공통 조상이다.

이렇게 찾은 공통 조상을 res 값으로 저장

이제 해당 노드로 부터 자식 노드가 얼마나 있는지 찾는다.

=> findCnt 메소드로 만들어서 결과 찾기

 

전체 코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution_No11_공통조상 {
    static class Node  {
        int data, parent;
        List<Integer> child;
        public  Node(){
            data = 0;
            child = new ArrayList<>();
            parent = 0;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data+
                    ", parent=" + parent +
                    ", child=" + child +
                    '}';
        }
    }
    static int V, E, no1, no2, cnt;
    static Node[] tree;
    static LinkedList<Integer> pa;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for (int testCase = 1; testCase <= T; testCase++) {
            st = new StringTokenizer(br.readLine());
            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());
            no1 = Integer.parseInt(st.nextToken());
            no2 = Integer.parseInt(st.nextToken());
            tree = new Node[V+1];
            for (int i = 1; i <= V; i++) {
                tree[i] = new Node();
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < E; i++) {
                int parent = Integer.parseInt(st.nextToken());
                int child = Integer.parseInt(st.nextToken());
                tree[parent].child.add(child);
                tree[parent].data = parent;
                tree[child].parent = parent;
            }
            //// 입력 완료
            //// 이제 부모를 찾아 넣는 메소드 구현
            LinkedList<Integer> no1P = new LinkedList<>();
            pa = new LinkedList<>();
            findParent(no1);
            pa.add(no1);
            no1P.addAll(pa);
            pa = new LinkedList<>();
            findParent(no2);
            LinkedList<Integer> no2P = new LinkedList<>();
            no2P.addAll(pa);
            int size = Math.min(no1P.size(), no2P.size());
            int res = 0;
            for (int i = 1; i < size; i++) {
                if (no1P.get(i).equals(no2P.get(i))) {
                    res = no1P.get(i);
                }else break;
            }
            cnt = 0;
            findCnt(res);
            sb.append("#").append(testCase).append(" ").append(res).append(" ").append(cnt).append("\n");
        }
        System.out.println(sb);
    }
    private static void findParent(int cur){
        int parent = tree[cur].parent;
        if (parent != 0) {
            findParent(parent);
        }
        pa.add(parent);
    }
    private static void findCnt(int cur){
        Node node = tree[cur];
        cnt++;
        for (int child : node.child) {
            findCnt(child);
        }
    }
}

 

제출 결과