문제

이해

일반적으로 우리 나라의 가족 관계에 사용되는 촌 수를 계산하려고 한다.

촌 수는 부모 자식 관계를 기준으로 계산된다.

입력으로는 전체 사람의 수가 주어지고 촌 수를 계산해야 할 두 사람의 번호가 주어진다.

다음으로는 위 두 사람이 포함되어 있는 가족의 관계를 입력받는다.

M줄에 걸쳐 x, y를 입력받는데 이 때, x는 부모, y는 자식이 된다.

단, 문제의 경우 부모는 최대 한 명만 주어진다.

접근

일반적인 가족 관계는 위 그림과 같이 자료구조 중 트리와 같은 형태를 띈다.

가족 관계를 트리에 비유한다면 촌 수는 어떻게 계산할 수 있을까? 바로 노드 간의 거리로 계산할 수 있다.

따라서, 두 사람의 촌 수는 두 사람의 트리 상 거리를 계산하여 구할 수 있다.

그렇다면 문제와 같이 트리의 부모 자식 정보만 입력받아 어떻게 트리로 구현할 수 있을까?

이에 내가 선택한 표현방법은 연결리스트 방식이다.

    static class node {
        int num;
        node parent;
        ArrayList<node> children;

        public node(int num) {
            this.num = num;
            this.children = new ArrayList<>();
        }

        public void set_parent(node parent) {
            this.parent = parent;
        }

        public void add_child(node child) {
            this.children.add(child);
        }
    }

node는 각 사람에 해당되며 현재 자신의 번호, 부모 (부모는 최대 1명), 자식들을 멤버로 갖는다.

자식의 경우 둘 이상 존재할 수 있기 때문에 ArrayList형으로 동적으로 저장하도록 하였다.

초기에 번호에 해당하는 노드들을 생성해주고 M줄의 입력에서 받은 가족 관계를 node 클래스의 메소드를 이용해 설정해주면 트리를 구현할 수 있다.

다음으로는 촌 수의 계산 방법이다.

위에서 설명했듯이 거리를 계산하면 되기 때문에 DFS를 실행하면 되겠다. 물론, BFS로 실행해도 된다.

한 가지 생각해야 하는 점은 가족 관계는 그래프 형식이 아닌 트리 구조를 띄기 때문에 DFS 수행 시 노드를 방문할 때 항상 최단거리로 방문한다.

따라서, 굳이 방문한 노드의 방문 여부를 다시 원상태로 돌려놓을 필요가 없다.

코드

package java_baekjoon;

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

public class prob2644 {
    static int N;
    static int A;
    static int B;
    static boolean[] visited;
    static node[] node_arr;

    static class node {
        int num;
        node parent;
        ArrayList<node> children;

        public node(int num) {
            this.num = num;
            this.children = new ArrayList<>();
        }

        public void set_parent(node parent) {
            this.parent = parent;
        }

        public void add_child(node child) {
            this.children.add(child);
        }
    }

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

        N = Integer.parseInt(br.readLine());
        node_arr = new node[N + 1];
        for(int i=1;i<=N;i++){
            node_arr[i] = new node(i);
        }
        visited = new boolean[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        
        int M = Integer.parseInt(br.readLine());
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());

            int nodeA = Integer.parseInt(st.nextToken());
            int nodeB = Integer.parseInt(st.nextToken());

            node_arr[nodeA].add_child(node_arr[nodeB]);
            node_arr[nodeB].set_parent(node_arr[nodeA]);
        }

        visited[A] = true;
        dfs(node_arr[A], 0);

        if(!visited[B]){
            System.out.println(-1);
        }
    }

    static void dfs(node now, int depth) {
        if (now.num == B) {
            System.out.println(depth);
            return;
        }

        if (!Objects.isNull(now.parent) && !visited[now.parent.num]) {
            visited[now.parent.num] = true;
            dfs(now.parent, depth + 1);
        }

        for (int i = 0; i < now.children.size(); i++) {
            if (!visited[now.children.get(i).num]) {
                visited[now.children.get(i).num] = true;
                dfs(now.children.get(i), depth + 1);
            }
        }
    }
}

결과