[백준(JAVA)] 2644번: 촌수계산

세하·2026년 3월 15일

Java 백준

[백준] 문제풀이

목록 보기

86/94

문제

✔ 난이도 - Silver 2

설명

bfs
나의 주변부터 연결된애들 쭉 탐색하는데 그때마다 각각에 대한 촌수 계산
최단거리 탐색과 동일함
visited 여부 당연히 체크해야하고, queue에는 현재 누군인지와, 그 사람과의 촌수를 저장

⚠️ BFS에서 거리를 계산할 때는 "현재 노드의 거리 + 1" 이 다음 노드의 거리가 되어야 함
내(node)가 출발점에서 K만큼 떨어져 있다면, 내 옆(next)은 무조건 K+1만큼 떨어져 있다.

풀이

public class Main {

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

        int N = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int A = Integer.parseInt(str[0]);
        int B = Integer.parseInt(str[1]);
        int M = Integer.parseInt(br.readLine());

        ArrayList<Integer>[] graph = new ArrayList[N+1];
        for (int i = 1;  i <= N; i++){
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0;  i < M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
        // 부모자식 관계그래프 완성

        sb.append(bfs(N, graph, A, B));
        System.out.println(sb);
    }

    private static int bfs(int N, ArrayList<Integer>[] graph, int me, int target){
        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[N+1];

        queue.offer(new int[] {me, 0});
        visited[me] = true;

        while (!queue.isEmpty()){
            int[] tmp = queue.poll();
            int person = tmp[0];
            int count = tmp[1];

            if (person == target) return count;

            for (int p : graph[person]) {
                if (visited[p]) continue;

                queue.offer(new int[] {p, count+1});
                visited[p] = true;
            }
        }

        return -1;
    }
}

⏰ 시간복잡도

$O(N+M)$

방문하는 노드 수 ( $N$ ): visited 배열을 사용하여 한 번 방문한 사람은 다시 큐에 넣지 않는다. 즉, 모든 사람은 최대 한 번씩만 큐에 들어갔다 나옴. ( $O(N)$ )
탐색하는 간선 수 ( $M$ ): 각 사람을 큐에서 꺼낼 때마다 그 사람과 연결된 친척들(graph[person])을 확인한다. 모든 사람의 친척 관계를 다 훑어보는 횟수는 결국 전체 관계 수인 $M$ 에 비례함. ( $O(M)$ )
최종 복잡도: 두 작업을 합쳐서 $O(N + M)$

$O(N)$ 이 아닌 이유?
만약 모든 사람이 서로서로 복잡하게 얽혀 있다면(예: 한 명에게 친척이 99명인 경우), 한 노드를 꺼낼 때마다 99번을 훑어야 하죠? 그래서 단순히 노드 수( $N$ )만 생각하는 게 아니라 관계 수( $M$ )까지 고려하는 것이 더 정확하다.