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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class bok_11725 {

    static int n;
    static int[] parents;
    static boolean[] isVisited;
    static StringTokenizer st;
    static List<Integer> nodes[];


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        isVisited = new boolean[n+1];
        nodes = new ArrayList[n+1];
        parents= new int[n+1];

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

        //연결된 노드끼리 리스트에 추가해주기
        for (int i=0; i<n-1; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            nodes[u].add(v);
            nodes[v].add(u);
        }

        dfs(1);

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

    }

    private static void dfs(int index) {
        isVisited[index] = true;
        for (int current : nodes[index]){
            if(!isVisited[current]){
                parents[current] = index;
                dfs(current);
            }
        }
    }
}

• 배열을 이용해서 해당 배열에 ArrayList형태의 자료구조로 자식 노드를 넣어준다.
• 다 넣은 자료를 이용해서 dfs를 사용해서 해당 인덱스에 해당하는 부모 노드를 저장 한다. 

---

1. root를 1로 지정

2. 연결된 노드들을 각 index를 기준으로 list에 넣어주기

3. dfs를 사용해 해당 index에 있는 연결 노드들을 다 방문하며 부모 노드를 찾아 index 기준으로 저장해주기

  - 2의 부모가 4라면 parent[2] = 4 가 들어갈 수 있게 진행