트리의 부모 찾기 11725

https://www.acmicpc.net/problem/11725

샘플 예제를 그림으로 그려보고
부모의 정보를 넣을 배열을 만들었고
처음에는 너비탐색 하면서 동시에 Queue 에 추가할때마다 배열에 부모값을 넣기로 생각했는데
깊이우선탐색을 연습할겸 깊이우선탐색으로 해결하였다
Stack 에 넣기전에 부모정보를 넣을 배열에 부모값을 넣어줬다

시간복잡
O(N)

import java.io.*;
import java.util.*;

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

        int N = Integer.parseInt(br.readLine());
        int[] parent = new int[N+1];//인덱스는 자녀노드, 값은 부모노드
        boolean[] visit = new boolean[N+1];
        ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
        for(int i = 0; i < N+1; ++i)
            tree.add(new ArrayList<>());

        String[] input;
        for(int i = 0; i < N-1; ++i)
        {
            input = br.readLine().split(" ");
            tree.get(Integer.parseInt(input[0])).add(Integer.parseInt(input[1]));
            tree.get(Integer.parseInt(input[1])).add(Integer.parseInt(input[0]));
        }

        dfs(1, tree, visit, parent);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < parent.length; ++i)
        {
            if(i > 1)
                sb.append(parent[i] + "\n");
        }

        System.out.println(sb);
    }

    private static void dfs(int root, ArrayList<ArrayList<Integer>> tree, boolean[] visit, int[] parent)
    {
        Stack<Integer> stack = new Stack<>();

        stack.push(root);
        visit[root] = true;

        while(stack.isEmpty() == false)
        {
            int cur = stack.peek();
            ArrayList<Integer> curNode = tree.get(cur);
            boolean noVisit = true;
            for(int element : curNode)
            {
                if(visit[element] == false)
                {
                    parent[element] = cur;

                    visit[element] = true;
                    stack.push(element);
                    noVisit = false;
                    break;
                }
            }
            if(noVisit)
                stack.pop();
        }
    }
}