BOJ) 촌수 계산

촌수 계산

2644번: 촌수계산

 

풀이

 

문제 의미대로 촌수를 계산하는 코드를 짜야한다.

다른 질문게시판을 보면 여러 알고리즘을 언급하고, 2차원 배열을 통해 푸는 것 같았다.

2차원 배열까지 갈 필요가 없다고 느껴서 1차원 배열로 풀었다.

 

우선 주어지는 값을, 1차원 배열에 저장했다.

저장하는 배열의 index는 자식 노드의 번호가 되고, value는 부모 노드를 입력해줬다.

부모 노드의 경우 자식 노드가 1개 이상 존재할 수 있기 때문이다.

 

그리고, 해당 노드들이 parent를 따라 움직이는 move 2차원 배열을 만들어 줬다.첫번째 인덱스에는 탐색의 기준 노드인 자식 노드의 인덱스, 두번째 인덱스는 부모 노드의 인덱스를 저장했다.촌수를 찾아야하는 left와 right에 대해서 부모노드를 타고 가면서 move 배열에 움직인 횟수를 저장해줬다.(부모 =1, 조부모 =2)

 

이후, 모든 인덱스를 검사하면서 left와 right가 동시에 특정 노드에 방문한 적이 있으면 두 move의 합을 리턴해 답을 구해줬다.

쉽게 풀 수 있는 문제였는데, 형제의 관계를 1촌으로 예외처리했던 부분이 있어서 정답을 제출하는데 오래걸렸다..

싸이월드 때문인가... 1촌을 왜 지정했는지 모르겠다.. ㅠ

 

 

코드

 

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

public class Main {
    final static int fail = -1, nothing =0;

    static int[][] move;
    static int[] familyTree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int left = Integer.parseInt(st.nextToken());
        int right = Integer.parseInt(st.nextToken());
        familyTree = new int[n+1];

        int m = Integer.parseInt(br.readLine());
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int parents = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            familyTree[child] = parents;
        }
        br.close();
        solution(n, left, right);
    }

    private static void solution(int n, int left, int right) {
        int result;

        initMove(n);

        result = getResult(left,right, n);
        if(result == Integer.MAX_VALUE)     result = fail;

        System.out.println(result);
    }

    private static void initMove(int n) {
        move = new int[n+1][n+1];
        for(int i=1; i<=n; i++) {
            Arrays.fill(move[i], -1);
        }
    }

    private static int getResult(int left, int right, int n) {
        int result =Integer.MAX_VALUE;
        findParents(left);
        findParents(right);
        for(int i=1; i<=n; i++) {
            if(move[left][i] !=-1 && move[right][i] !=-1) result = Math.min(result, move[right][i] + move[left][i]);
        }
        return result;
    }

    private static void findParents(int child) {
        LinkedList<Integer> treeMove = new LinkedList<>();
        treeMove.offer(familyTree[child]);
        move[child][familyTree[child]] = 1;
        int cnt =1;
        if(familyTree[child] ==0)   move[child][child] = nothing;


        while(!treeMove.isEmpty()) {
            int now = treeMove.poll();
            int parent = familyTree[now];
            if(parent !=nothing) {
                move[child][parent] = ++cnt;
                treeMove.offer(parent);
            }
        }
    }
}