[백준 Silver 2] 2644 촌수 계산 - Java

문제링크 : https://www.acmicpc.net/problem/2644

2644번: 촌수계산

 

접근 과정 : 

• 두 사람간의 촌수를 계산하는데, 두 사람의 공통 조상 중 가장 가까운 공통 조상을 찾아야 한다.
• 즉, 공통 조상이 여럿 있을 수 있다는 것을 인지해야 한다. (난 이 부분을 인지하지 못해 처음에 실패했다.)
• 나와 친척의 공통조상은 조부모, 증조 조부모, 고조 조부모가 될 수 있기 때문에!!!! 가장 가까운 공통 조상을 찾아야 한다!!
• 먼저 입력으로 주어진 부모와 자식 관계를 배열로 표시했다.  parent[자식] = 부모
• 주어진 두 사람중, 먼저 A의 조상과 그 거리를 모두 Map에 담았다.
• 나머지 B의 조상을 찾아가면서, 만약 그 조상이 A의 조상 Map에 포함되어 있다면 그 때, 두 거리를 더해서 계산.

 

소스 코드 및 결과 :

/* 
    촌수계산
*/

import java.io.*;
import java.util.*;

public class BOJ2644 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(br.readLine());

        root = new int[N + 1];

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());

            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());

            root[child] = parent;
        }

        distance = -1;
        parents = new HashMap<>();

        setRoot(a, 0);
        findDistance(b, 0);

        System.out.println(distance);

    }

    static int distance;
    static int[] root;
    static HashMap<Integer, Integer> parents;

    static void setRoot(int child, int d) {

        parents.put(child, d);

        if (root[child] == 0) {
            return;
        }

        setRoot(root[child], d + 1);

    }

    static void findDistance(int child, int d) {

        if (parents.containsKey(child)) {
            distance = parents.get(child) + d;
            return;
        }

        if (root[child] == 0) {
            return;
        }

        findDistance(root[child], d + 1);
    }
}

 

P.S 

'가장 가까운 공통 조상' 이라는 것을 잊고 풀어서 처음에 실패했었다...

집중!!!!!!!!