bfs에서 각 레벨의 노드 수 찾기

Question

N 개의 노드로 구성된 트리를 받았습니다. 트리는 N 노드와 N-1 에지로 구성된 완전 연결된 그래프입니다. 이 트리의 노드는 1에서 N까지 인덱싱됩니다. 인덱싱 된 노드 1이이 트리의 루트 노드라고 가정합니다. 루트 노드는 트리의 1 단계에 있습니다. 나무와 하나의 정수 x가 주어질 것입니다. 레벨 x에 누워있는 노드의 수를 찾아야합니다.

입력 형식

첫 번째 줄은 트리의 노드 수를 나타내는 하나의 정수 N 구성되어 있습니다. 다음 n-1 라인 각각은 2 개의 정수 a와 b로 구성되며, 노드 a와 노드 b 사이의 비 방향성 에지를 나타냅니다. 다음 행은 단일 정수 x로 구성됩니다.

출력 형식

당신은 레벨 X에서 노드의 수를 나타내는 하나의 정수를 인쇄해야합니다.

---

아래 코드는 내가 작성한 코드이며 올바르지 않습니다. 오류를 찾도록 도와주세요.

첫 번째 문제는 코드가 종료되지 않을 수 있다는 것입니다 :

import java.util.ArrayList; 
import java.util.LinkedList; 
import java.util.Scanner; 

public class LevelNodes { 
    public static ArrayList[] adj; 
    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     int N = sc.nextInt(); 
     boolean[] visites = new boolean[N]; 
     ArrayList[] adj = new ArrayList[N]; 
     for(int j=0;j<N;j++){ 
      adj[j] = new ArrayList(); 
     } 
     for(int i = 0;i < (N-1) ;i++){ 
      int a = sc.nextInt(); 
      int b = sc.nextInt(); 
      adj[a-1].add(b); 
      adj[b-1].add(a); 
     } 
     int level = sc.nextInt(); 
     int counter = 0; 
     LinkedList list = new LinkedList(); 
     list.add(1); 
     counter++; 
     while(!list.isEmpty()){ 
      int n = (Integer) list.poll(); 
      for(int x = 0; x< adj[n-1].size();x++){ 
       list.add(adj[n-1].get(x)); 
      } 
      counter++; 
      if(counter == level){ 
       System.out.println(list.size()); 
       break; 
      } 

     } 
    } 

} 

Answer 1

코드에서 문제가 있습니다. 이는 u-> v 및 v-> u 양쪽 가장자리를 인접 목록에 추가하기 때문입니다. 따라서 목록에서 u를 폴링하고 이웃을 추가 할 때마다 v를 목록에 추가합니다. 마찬가지로 v를 폴링하고 이웃을 추가 할 때마다 u를 목록에 다시 추가합니다. 부울 배열 visited을 유지하고 목록에 u를 추가 할 때마다 visited[u]=true을 설정해야합니다. 이렇게하면 검사하지 않은 노드 만 스캔 목록에 추가 할 수 있습니다.

또 다른 주요 문제는 while 루프에 있습니다. 새 노드를 방문 할 때마다 레벨 카운터 변수 counter++;을 증가시킵니다. 아래의 트리를 고려하고 레벨 2 (마지막 레벨)에서 노드 수를 찾아야한다고 가정합니다.

 1 
    /\ 
    2 3 
/\/\ 
4 5 6 7 

처음에는 목록에 1과 counter=1이 포함되어 있습니다. 첫 번째 반복에서 목록에서 1을 폴링하고 이웃을 추가합니다 (2와 3).이 단계에서 counter=2. 다음 두 번의 반복에서 목록에서 2, 3을 제거하고 이웃을 추가 한 다음 매번 counter을 증가시킵니다. 따라서 두 번째 레벨에 도달하면 counter은 4가됩니다. If 문은 절대로 실행되지 않습니다.

이 문제를 해결하려면 현재 수준에서 모든 노드를 처리했으면 counter을 증가시켜야합니다. 이를 수행하는 간단한 (테스트되지 않은) 방법은 두 번째 임시 목록을 사용하여 현재 레벨의 모든 노드의 이웃 노드를 유지하는 것입니다. 그런 다음 원래 목록이 비어있을 때마다 현재 레벨에서 모든 노드를 처리 한 것을 알게됩니다. 여기서 counter을 증가시키고 임시 목록의 모든 노드를 기본 목록으로 이동합니다.

while(!list.isEmpty()){ 
    int n = (Integer) list.poll(); 
    for(int x = 0; x< adj[n-1].size();x++){ 
     tmpList.add(adj[n-1].get(x)); 
    } 

    if(list.isEmpty()) { 
     if(counter == level){ 
      System.out.println(tmpList.size()); 
      break; 
     } 

     list.addAll(tmpList); 
     tmpList.clear(); 
     counter++; 
    } 
}