백준 2644번 - 촌수계산

코드

public class Baekjoon2644 {

    static List<Integer>[] arr;
    static int ans = -1;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int start = sc.nextInt();
        int end = sc.nextInt();
        int T = sc.nextInt();

        arr = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }
        for (int i = 0; i < T; i++) {
            int first = sc.nextInt();
            int second = sc.nextInt();
            arr[first].add(second);
            arr[second].add(first);
        }

        dfs(start, end, 0, new boolean[n + 1]);

        System.out.println(ans);
    }

    public static void dfs(int current, int end, int count, boolean[] visited) {
        if (current == end) {
            ans = count;
            return;
        }

        for (int next : arr[current]) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next, end, count + 1, visited);
                visited[next] = false;
            }
        }
    }

}

풀이

😊bfs와 dfs 두 가지 방법을 이용하여 풀 수 있는데 여기서는 dfs를 이용하여 풀었다.
입력 받은 값을 제외하고 dfs로직만을 확인하면 먼저 종료 조건은 현재 값이 end(목적지)에 도달하면 종료한다. 그렇지 않다면 dfs를 돌리는데 위에서 입력받은 값을 통해 해당 값과 연결된 값들을 확인한다. 이 때 이미 방문한 곳은 다시 방문 못하게 visited를 통해 해결하였다.

사실 위 문제에서 visited를 저런식으로 구현안하고 단 한번만 선언하고 해도 풀린다.(이렇게 푸는 것이 습관이 되서 이렇게 풀었다.)

출처 : 백준 -촌수계산