백준 2644 자바

 

BFS를 이용하여 풀었습니다.

간단하게 설명하자면

촌수 관계가 Node 역할을 합니다. 이것을 ArrayList에 담고

num과 num1이 몇 촌 사이인지 계산을 해야 합니다.

아래 BFS 구현은

일반적인 BFS문제와 비슷하지만 추가할 것은 int[] arr 배열을 이용해서 촌수 관계를 기록해놔야 합니다.

좀 쉽게 말하자면 어차피 3과 7의 관계를 볼 때 가까운 촌수부터 점점 멀어지므로 이전의 arr[q]에 + 1을 해주는 방식입니다. 

그리고 우리가 찾아야 할 num1과 q가 같다면 그대로 끝을 내주고, 다 찾아봤는데도 못 찾으면 기존의 result값인 -1을 출력하면 됩니다.

import java.util.*;
import java.io.*;
public class Main {

    static ArrayList<Integer>[] list;
    static boolean[] visited;
    static int M, num, num1;
    static int result = -1;
    static int[] arr;


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

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

        list = new ArrayList[N+1];
        arr = new int[N+1];
        visited = new boolean[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        num = Integer.parseInt(st.nextToken());
        num1 = Integer.parseInt(st.nextToken());

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

        for (int i = 1; i <= N; i++) {
            list[i] = 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[parent].add(child);
            list[child].add(parent);
        }
        BFS(num);
    }

    static void BFS(int R) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(R);

        visited[R] = true;
        while (!queue.isEmpty()) {
         int q = queue.poll();

         if (q == num1) {
             result = arr[q];
             break;
         }

         for (int i: list[q]) {
             if (!visited[i]) {
                 visited[i] = true;
                 arr[i] = arr[q]+1;
                 queue.add(i);
             }
         }
        }
        System.out.println(result);
    }
}