트리의부모노드찾기-1

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

public class 트리의부모찾기 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 노드 개수 입력

        // 트리 구조 표현을 위한 그래프 구현
        ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
        for (int i = 0; i < n; i++)
            tree.add(new ArrayList<>());

        // 그래프 입력
        for (int i = 0; i < n - 1; i++) {
            int n1 = sc.nextInt() - 1;
            int n2 = sc.nextInt() - 1;
            tree.get(n1).add(n2);
            tree.get(n2).add(n1);
        }

        boolean[] visited = new boolean[n]; // 방문 여부 확인용 배열
        int[] parentNode = new int[n]; // 부모 노드 저장 배열

        // BFS
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int v = queue.remove();
            for (int node : tree.get(v))
                if (!visited[node]) {
                    visited[node] = true;
                    queue.add(node);
                    parentNode[node] = v; // 부모 노드 찾은 후 저장
                }
        }

        // 루트 노드를 제외한 나머지 노드의 부모 노드 출력
        for (int i = 1; i < n; i++)
            System.out.println(parentNode[i] + 1);
    }

}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class 트리의부모노드찾기_1 {
    static LinkedList<Integer>[] arr;
    static LinkedList<Boolean>[] visited;
    static int N;
    static HashMap<Integer, Integer> tree = new HashMap<>(); // key는 child, value는 parent
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new LinkedList[N + 1];
        visited = new LinkedList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            arr[i] = new LinkedList<Integer>(); // i의 자식노드만 남기기
            visited[i] = new LinkedList<Boolean>();
        }
        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            arr[v1].add(v2);
            arr[v2].add(v1);
            visited[v1].add(false);
            visited[v2].add(false);

        }

        dfs(1);

        for (int i = 2; i <= N; i++) {
            sb.append(tree.get(i) + "\n");
        }
        System.out.print(sb.toString());

    }

    static void dfs(int parent) {

        for (int i = 0; i < arr[parent].size(); i++) {
            if (!visited[parent].get(i)) {
                int child = arr[parent].get(i);
                if (!tree.containsKey(child))
                    tree.put(child, parent); // 자식 노드 추가

                visited[parent].set(i, true);
                int parentIdx = arr[child].indexOf(parent);
                visited[child].set(parentIdx, true);
                dfs(child);
                visited[parent].set(i, false);
                visited[child].set(parentIdx, false);

            }

        }

    }

}