[백준 11725] 트리의 부모 찾기 [java]

---

dfs를 이용하여 루트 노드부터 차례대로 아래로 내려가면서 문제를 해결한다.

 

- 1번이 루트노드로 정해졌으므로 1번부터 밑으로 내려가면 된다

- 리스트를 만들어 서로 연결된 노드들을 넣어준다.

- dfs 메소드에서 for문을 이용해 차례대로 노드들을 뽑아준다.

- 뽑은 노드들을 다시 dfs로 후출하면 된다.

 

* 위에서부터 차례대로 노드를 찾아가므로 부모배열을 만들고 dfs의 매개변수랑 연결된 값의 부모는 매개변수가 된다.

 

코드

package baekjoon;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class find_treeparent {

    static int n;
    static List<Integer>[] list;
    static boolean[] visit;
    static int[] parents;

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

        list = new ArrayList[n+1];
        parents = new int[n+1];
        visit = new boolean[n+1];

        for(int i = 1;i<=n;i++){
            list[i] = new ArrayList<>();
        }

        for(int i = 0; i<n-1;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            list[a].add(b);
            list[b].add(a);

        }
        dfs(1);
        for(int i = 2;i<=n;i++){
            System.out.println(parents[i]);
        }
    }

    public static void dfs(int v){
        visit[v] = true;

        for(int i : list[v]){
            if(!visit[i]){
                parents[i] = v;
                dfs(i);
            }
        }
    }
}