백준 2644번 촌수계산 JAVA

링크텍스트

설명

입력으로 사람 수와 촌수를 계산할 두 사람의 번호, 그리고 부모-자식 관계 개수를 받았다. 각 사람별로 부모와 자식 간의 관계를 양방향 간선으로 그래프에 저장했다.
방문 여부를 체크할 배열과 각 사람까지의 촌수를 기록할 배열을 초기화했다. BFS를 이용해 시작점에서부터 탐색을 시작했다.
큐에서 현재 노드를 꺼내 연결된 이웃 노드들을 확인했다. 방문하지 않은 이웃 노드를 방문 처리하고 현재 노드 촌수에 1을 더한 값을 갱신했다.
갱신한 노드를 큐에 넣어 다음 탐색 대상으로 추가했다. 탐색을 반복하며 목표 노드까지의 최단 거리를 계산했다. 탐색이 끝나면 목표 노드의 촌수를 출력했다. 만약 목표 노드에 도달하지 못하면 -1을 출력하도록 했다.
시간복잡도: O(N+M), 공간복잡도: O(N+M)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {
        static int n,m;
        static ArrayList<Integer>[] arr;
        static int [] dist;
        static boolean [] check;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        arr = new ArrayList[n+1];
        check = new boolean[n+1];
        dist = new int[n+1];
        Arrays.fill(dist, -1);

        for(int i=1;i<=n;i++){
            arr[i] = new ArrayList<>();
        }

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

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

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

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            arr[x].add(y);
            arr[y].add(x);
        }

        dfs(start);

        System.out.println(dist[end]);
        
    }

    public static void dfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        check[start] = true;
        dist[start] = 0;

        while(!q.isEmpty()){
            int cur = q.poll();

            for(int next : arr[cur]){
                if(!check[next]){
                    check[next]=true;
                    dist[next] = dist[cur]+1;
                    q.offer(next);
                }
            }
        }
    }
}

DFS

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

public class Main {
    static int n, m;
    static ArrayList<Integer>[] arr;
    static boolean[] check;
    static int end;
    static int answer = -1;

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

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

        arr = new ArrayList[n + 1];
        check = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }

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

        int start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            arr[x].add(y);
            arr[y].add(x);
        }

        dfs(start, 0);

        System.out.println(answer);
    }

    public static void dfs(int current, int depth) {
        check[current] = true;

        if (current == end) {
            answer = depth;
            return;
        }

        for (int next : arr[current]) {
            if (!check[next]) {
                dfs(next, depth + 1);
            }
        }
    }
}