[JAVA] 백준 2644번 촌수계산

https://www.acmicpc.net/problem/2644

코드

방향 그래프를 설정하고 DFS 탐색을 진행합니다.

탐색 종료 조건으로 현재 시작 노드(s)와 끝 노드(e)가 x, y와 일치하면 종료합니다.

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

public class Main {

    static int n, m;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int x, y;
    static int result = -1;


    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());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());

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

        visited = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            graph.get(num1).add(num2);
            graph.get(num2).add(num1);
        }

        dfs(x, y, 0);
        System.out.println(result);
    }

    static void dfs(int s, int e, int cnt) {
        if (s == e) {
            result = cnt;
            return;
        }

        visited[s] = true;
        for (int v : graph.get(s)) {
            if (!visited[v]) {
                dfs(v, e, cnt + 1);
            }
        }

    }
}