[백준] 2644번. 촌수계산(DFS)

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

class Villages {
    static final int MAX = 100 + 10;
    static boolean[][] graph;
    static boolean visited[];
    static int N, M, start, end, answer;
    
    public static void dfs(int idx, int count) {
        visited[idx] = true;
        if(idx == end) {
            answer = count;
            return;
        }

        for(int i = 1; i <= N; i++) {
            if(visited[i] == false && graph[idx][i]) {
                dfs(i, count + 1);
            }
        }
    }

    public static void main(String args[]) throws IOException {
        // 0. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

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

        // 1. graph에 연결 정보 채우기
        graph = new boolean[MAX][MAX];
        visited = new boolean[MAX];
        answer = -1;


        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph[x][y] = true;
            graph[y][x] = true;
        }

        // 2. dfs(재귀 함수)호출 하기
        dfs(start, 0);

        // 3. 출력하기
        bw.write(String.valueOf(answer));

        bw.close();
        br.close();
    }
}