트리의 부모 찾기 - 백준(11725, 그래프 탐색, BFS / DFS)

🎯 단지번호붙이기

트리의 부모 찾기 - 11725, 그래프 탐색, 실버2

---

🧐 알고리즘[접근방법]

1.tree의 부모 - 자식 정보가 담긴 ArrayList tree배열 선언, 부모 정보가 담긴 parent 배열 선언, 부모 된 적이 있는지 확인하는 check 배열 선언

2. tree배열에 부모 - 자식 정보 저장

3. 1번 tree부터 순회 후 자식 노드는 부모 정보를 parent 배열에 저장, 순회한 check 배열 true로 변경

4
. parent의 2번 노드부터 출력

---

👨‍💻 소스

BFS 소스

import java.util.*;

public class Main {

  public static int N;  // Node 개수
  public static ArrayList<Integer>[] tree;  // 트리
  public static int[] parent; // 부모 정보 배열
  public static boolean[] check; // 부모 여부
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    N = sc.nextInt();
    sc.nextLine();
    
    tree = (ArrayList<Integer>[]) new ArrayList[N + 1];
    for(int i = 1 ; i <= N ; i++) {
      tree[i] = new ArrayList<Integer>();
    }
    
    for(int i = 0 ; i < N - 1 ; i++) {
      int left = sc.nextInt();
      int right = sc.nextInt();
      
      tree[left].add(right);
      tree[right].add(left);
    }
    
    parent = new int[N + 1];
    check = new boolean[N + 1];

	BFS();
    
    for(int i = 2 ; i < parent.length ; i++){
      System.out.println(parent[i]);
    }
    
    sc.close();
    
  }
  
  public static void BFS() {
    
    Queue<Integer> q = new LinkedList<Integer>();
    q.add(1);
    check[1] = true;
    
    while(!q.isEmpty()) {
      int n = q.poll();
      
      for(int i = 0 ; i < tree[n].size() ; i++) {
        int now = tree[n].get(i);
        if(!check[now]) {
          parent[now] = n;
          check[n] = true;
          q.add(now);
        }
      }
    }
   
  }

}

DFS 소스

import java.util.*;

public class Main {

  public static int N;  // Node 개수
  public static ArrayList<Integer>[] tree;  // 트리
  public static int[] parent; // 부모 정보 배열
  public static boolean[] check; // 부모 여부
  
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    
    N = sc.nextInt();
    sc.nextLine();
    
    tree = (ArrayList<Integer>[]) new ArrayList[N + 1];
    for(int i = 1 ; i <= N ; i++) {
      tree[i] = new ArrayList<Integer>();
    }
    
    for(int i = 0 ; i < N - 1 ; i++) {
      int left = sc.nextInt();
      int right = sc.nextInt();
      
      tree[left].add(right);
      tree[right].add(left);
    }
    
    parent = new int[N + 1];
    check = new boolean[N + 1];

    DFS(1);
    
    for(int i = 2 ; i < parent.length ; i++){
      System.out.println(parent[i]);
    }
    
    sc.close();
    
  }

 public static void DFS(int index) {
    
    check[index] = true;
    
    for(int i = 0 ; i < tree[index].size() ; i++) {
      int now = tree[index].get(i);
      
      if(!check[now]) {	// 현재 tree 노드가 부모였던 적이 없을 때
        parent[now] = index;
        check[index] = true;
        DFS(now);
      }
    }
  }
 
}

---

🏅 결과

BFS 결과

DFS 결과

📖 관련 지식