(백준 #11725) (자바) (트리) (DFS) 트리의 부모 찾기

11725: 나무의 부모 찾기(acmicpc.net)

설명

• num1과 num2는 연결되어 있으므로 tree(num1)에 num2를, tree(num2)에 num1을 넣어야 합니다.
  
  
• 결과적으로 Tree(1) = {6, 4} / Tree(2) = {4} / Tree(3) = {6, 5} / Tree(4) = {1, 2, 7} / Tree( 5 ) ) = {3} / 트리(6) = {1, 3} / 트리(7) = {4}.
• dfs(깊은 우선 검색)를 구현하려면 스택을 방문했는지 확인하기 위해 방문 배열을 만들고 출력에 대한 부모 노드를 포함하는 부모 배열을 만듭니다.
  
  
  1. 먼저 스택에 1을 올려 루트 노드를 1로 표시하고 Visited를 true로 변경합니다.
     
     
  2. tree(1)은 6과 4를 포함하므로 parent(6) = 1이고 parent(4) = 1입니다.
     
     
  3. tree(4)의 경우 1, 2, 7이 포함되지만,visited(1) = true이므로 parent(1) = 4는 발생하지 않는다.
     
     
  4. 스택에서 5가 제거될 때까지 반복합니다.
     
     
• 노드 2에서 인쇄하도록 지시했으므로 2에서 for 문을 시작합니다.
  
  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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()); // 노드의 개수

        // 인접 리스트 구성
        ArrayList<Integer>() tree = new ArrayList(n + 1);
        for (int i = 1; i <= n; i++) {
            tree(i) = new ArrayList<>();
        }

        // tree 에 값 넣기
        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            tree(num1).add(num2);
            tree(num2).add(num1);
        }

        // dfs
        int() parent = new int(n + 1);
        boolean() visited = new boolean(n + 1);
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        visited(1) = true;
        while (!
stack.isEmpty()) {
            int cur = stack.pop();

            for (int child : tree(cur)) {
                if (!
visited(child)) {
                    stack.push(child);
                    parent(child) = cur;
                    visited(child) = true;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            System.out.println(parent(i));
        }
    }
}