트리의 부모 찾기(백준 11725) - DFS

핵심

DFS로 내려가면서, 내가 어디서 왔는지(=부모노드) 기록

visited[current] = true;
parent[next] = current;
dfs(next);

정답

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

public class Main {

    static ArrayList<Integer>[] tree; // 트리(인접 리스트)
    static boolean[] visited;         // 방문 여부
    static int[] parent;              // 각 노드의 부모 저장

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

        int n = Integer.parseInt(br.readLine()); // 노드 개수

        tree = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        parent = new int[n + 1];

        // 인접 리스트 초기화
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }

        // 간선 입력 (무방향)
        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            tree[a].add(b);
            tree[b].add(a);
        }

        // 1번 노드를 루트로 DFS 시작
        dfs(1);

        // 2번 노드부터 부모 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            sb.append(parent[i]).append('\n');
        }

        System.out.print(sb);
    }

    static void dfs(int current) {
        visited[current] = true; // 현재 노드 방문 표시

        for (int next : tree[current]) {
            if (!visited[next]) {        // 아직 방문 안 했으면
                parent[next] = current; // current가 next의 부모
                dfs(next);               // 다음 노드로 DFS
            }
        }
    }
}