[JAVA] 백준 2644_촌수계산

 

[문제링크]

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

 

📌 문제 탐색하기

그래프 문제로 사람들을 노드라고 생각하고 그래프로 표현이 가능하다. ( 양방향 관계 )

두 노드 간 최단 경로를 참색하여 촌수를 계산하는 문제이다. 만약에 노드가 연결되어 있지 않은 경우 -1을 출력한다.

📌 가능한 시간복잡도 

각각 최대 한번씩만 방문하기 때문에 시간복잡도는 O(N)이다.

📌 코드 설계하기

탐색하는 방법이 DFS인지 BFS인지에 따라서 풀이가 달라지는데,,, 효율적인 문제풀이 방식이 어떤 방식인지 고민됨.

 

BFS 사용해서 문제 풀이 진행

visited[] 배열을 만들어서 방문여부를 저장하는 배열 만들기

그리고 큐를 사용해서 현재 탐색하고 있는 노드와 촌수를 저장하기.

 

📌 정답 코드

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); 
        int personA = sc.nextInt();  
        int personB = sc.nextInt();  
        int m = sc.nextInt();  

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int parent = sc.nextInt();
            int child = sc.nextInt();
            graph.get(parent).add(child);
            graph.get(child).add(parent);  
        }

       
        int result = bfs(graph, n, personA, personB);
        System.out.println(result);

        sc.close();
    }


    private static int bfs(List<List<Integer>> graph, int n, int start, int target) {
        boolean[] visited = new boolean[n + 1];

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {start, 0}); 

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int node = current[0];
            int distance = current[1];

            if (node == target) {
                return distance;
            }
            visited[node] = true;

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    queue.add(new int[] {neighbor, distance + 1});
                }
            }
        }
        return -1;
    }
}