[백준 11725번][Java][Tree][DFS] 트리의 부모 찾기

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이

• 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} / tree[6] = {1, 3} / tree[7] = {4} 형태로 저장된다.
  
  
• dfs (depth first search) 를 구현하기 위해 stack과 방문했는지 확인하기 위해서 visited 배열을 생성하고, 출력을 위해 부모 노드를 담아둘 parent 배열을 생성한다.
  
  
  1. 먼저, root 노드를 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번 노드부터 출력하라고 했으므로 for문을 2부터 시작하도록 한다.

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]);
        }
    }
}