99클럽 코테 스터디 8일차 TIL - 백준 2644 촌수계산

Problem

1. 촌수를 계산

Input

1. n (1~100): 사람의 수
2. a b: 촌수계산이 필요한 두 사람의 번호
3. m(??): 부모 관계의 개수
4. x y: x가 부모, y가 자식

Output

1. a b 의 촌수관계 (관계가 없으면 -1)

Solve

1. 양향 노드를 생성
2. a에서 b 로 가는 노드를 찾아 카운트를 세어 출력.

Code

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

public class BOJ_2644_촌수계산 {

    static int N, A, B, M, answer;
    static List<List<Integer>> list = new ArrayList<>();
    static boolean[] visit;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());

        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }

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

            list.get(parent).add(child);
            list.get(child).add(parent);
        }

        visit = new boolean[N + 1];


        answer = -1;
        dfs(A, 0);
        System.out.println(answer);
    }

    static void dfs(int from, int count) {
        if (from == B) {
            answer = count;
            return;
        }
        visit[from] = true;

        int size = list.get(from).size();

        for (int i = 0; i < size; i++) {
            int next = list.get(from).get(i);

            if(!visit[next]) dfs(next, count + 1);
        }

    }
}