99클럽 코테 스터디 8일차 TIL (2644번: 촌수계산)

문제

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

---

학습 키워드

• BFS

 

시도

• (성공) 촌수를 계산해야하는 두 번호(a, b)의 조상까지 탐색하면서 같은 조상이 있는 지점까지 탐색한다. 그 다음, 두 번호(a, b)에서부터 같은 조상의 위치까지 1씩 더해가면서 거리를 찾는다.

• (성공) a부터 시작해서 b까지 BFS를 통해 거리를 구한다.

풀이 및 코드

• visited: 이미 탐색한 정점은 다시 탐색하지 않기 위해서 필요한 배열
• distance: a부터 시작해서 각 정점에 도달했을 때, 거리가 몇인지 저장하는 배열
• 현재 정점에서 가까운 정점부터 시작해서 탐색하고, 각 정점에 도달할 때마다 거리를 저장한다. 만약 목적지에 도달했다면 해당 목적지의 거리를 반환하고, 목적지에 도달하지 못 했다면 -1을 반환한다.

import java.util.*;

public class Main {

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

       int n = sc.nextInt(); // 전체 사람의 수
       int a = sc.nextInt(); // 촌수를 계산해야하는 사람 A
       int b = sc.nextInt(); // 촌수를 계산해야하는 사람 B
       int m = sc.nextInt(); // 부모 자식들 간의 관계의 개수

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

       for (int i = 0; i < m; i++) {
          int x = sc.nextInt(); // y의 부모
          int y = sc.nextInt(); // x의 자식
          graph[y].add(x);
          graph[x].add(y);
       }
       int answer = bfs(graph, a, b);
       System.out.println(answer);
    }

    private static int bfs(List<Integer>[] graph, int start, int target) {
       boolean[] visited = new boolean[graph.length];
       Queue<Integer> queue = new LinkedList<>();
       int[] distance = new int[graph.length];

       queue.offer(start);
       visited[start] = true;
       while (!queue.isEmpty()) {
          int current = queue.poll();
          if (current == target) {
             return distance[current];
          }
          for (int neighbor : graph[current]) {
             if (visited[neighbor]) {
                continue;
             }
             queue.offer(neighbor);
             distance[neighbor] = distance[current] + 1;
             visited[neighbor] = true;
          }
       }
       return -1;
    }
}