[백준 2644] 촌수계산(Java)

[백준 2644] 촌수계산(Java)

2644번: 촌수계산

2644번: 촌수계산

 

해결 방법

1트

부모자식간에는 1촌이라는 사실을 이용하여 DFS를 사용하여
문제에서 주어진 사람1(노드1)에서 시작해서 사람2(노드2)에 도달할때 깊이(depth)를 출력하면 됩니다.

촌수가 없으면(노드가 연결 안되있으면) -1을 출력하면 됩니다.

풀이

public class Quiz2644 {
    static int n;
    static int member1;
    static int member2;
    static int m;
    static List<Integer>[] list;
    // 촌수
    static int relation = -1;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        /**
         * 9        // 전체 사람수
         * 7 3      // 촌수를 계산해야하는 사람
         * 7        // 부모 자식들 간의 관계 갯수
         * 1 2      // 부모 자식간의 번호(서로 1촌)
         * 1 3
         * 2 7
         * 2 8
         * 2 9
         * 4 5
         * 4 6
         */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 노드 갯수
        n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        member1 = Integer.parseInt(st.nextToken());
        member2 = Integer.parseInt(st.nextToken());

        // 간선 갯수
        m = Integer.parseInt(br.readLine());

        // 인접 리스트 초기화
        list = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int member1 = Integer.parseInt(st.nextToken());
            int member2 = Integer.parseInt(st.nextToken());

            // 양방향
            list[member1].add(member2);
            list[member2].add(member1);
        }

        // 탐색 초기화
        visited = new boolean[n+1];
        visited[member1] = true;
        dfs(0, member1);

        System.out.print(relation);
        br.close();
    }

    private static void dfs(int depth, int member) {

        // 내가 찾는 사람이 나오면
        if(member == member2) {
            // 촌수 계산
            relation = depth;
            return;
        }

        for(Integer findMember : list[member]) {
            if(!visited[findMember]) {
                // 방문
                visited[findMember] = true;
                // 촌수 +1 증가
                dfs(depth + 1, findMember);
            }
        }
    }
}