요구사항

• 주어진 두 사람의 촌수를 계산하라

풀이법

1. 사람들간의 직접적인 연관관계가 주어진다.

   1 2
   1 3
   2 7
   2 8
   2 9
   4 5
   4 6

2. 해당 연관관계를 양방향 관계로 서로 연결시켜주면된다.

   1. 1번 과 2번이 이어져있으면
      1. 1번 친구 배열에 2번넣고
      2. 2번 친구 배열에 1번을 넣으면 된다.

3. 최종적으로

   1번의 친구들: [2, 3]
   2번의 친구들: [1, 7, 8, 9]
   3번의 친구들: [1]
   4번의 친구들: [5, 6]
   5번의 친구들: [4]
   6번의 친구들: [4]
   7번의 친구들: [2]
   8번의 친구들: [2]
   9번의 친구들: [2]

   • 가 완성된다.

4. 이후에 설정된 친구들 간의 관계에서

   • 7 3 시작친구 7 과 3 관계에서 몇 촌인지 구하면 된다.
   • 7 번 부터 시작해서
   • 큐에 ( 7번, count : 0 ) 을 담는다. (방문처리도 해야함)

     private static void bfs(int start, int target) {
         Queue<int[]> queue = new LinkedList<>();
         boolean[] visited = new boolean[TOTAL_PERSON_COUNT + 1];
         
         queue.offer(new int[]{start, 0});
         visited[start] = true;

   • 7번 친구에는

     while (!queue.isEmpty()) {
                 int[] current = queue.poll();
                 int node = current[0];
                 int count = current[1];
                 
                 if (node == target) {
                     System.out.println(count);
                     return;
                 }
                 
                 for (int next : GRAPH[node]) {
                     if (!visited[next]) {
                         queue.offer(new int[]{next, count + 1});
                         visited[next] = true;
                     }
                 }
             }

     for (int next : GRAPH[node]) {
         if (!visited[next]) {
             queue.offer(new int[]{next, count + 1});
             visited[next] = true;
         }
     }

     • 7번에 있는 친구의 배열을 순회하면
       • 2번 요 친구만 순회가 돌게된다.
       • 촌수를 계산할때 이미 들렀던 사람을 또 들르면 안되니, visited 에 이미 방문여부를 체크해야한다.
       • 이후에 한번 촌수계산했으니 + 1
       • 방문처리
     • (2,1) 만 큐에 담긴 상태가 된다.

• 향후

  if (node == target) {
      System.out.println(count);
      return;
  }

  • 에 따라 목표를 만나면 count 만 출력하면 된다