문제 설명

문제 분석

트리는 그래프 자료구조 중 하나의 형태이므로 그래프를 구현하는 방식을 사용할 수도 있고, 탐색 역시 그래프 탐색 알고리즘을 사용할 수 있다.

슈도코드

구현

public class 트리의부모찾기_11725 {
    static boolean[] visited;
    static int[] result;
    static List<Integer>[] tree;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken());

        visited = new boolean[N + 1];
        result = new int[N + 1];
        tree = new ArrayList[N + 1];
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 1; i < N; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int n1 = Integer.parseInt(tokenizer.nextToken());
            int n2 = Integer.parseInt(tokenizer.nextToken());
            tree[n1].add(n2);
            tree[n2].add(n1);
        }

        DFS(1); // 부모 노드부터 시작

        for (int i = 2; i <= N; i++) {
            System.out.println(result[i]);
        }
    }

    static void DFS(int num) {
        visited[num] = true;
        for (int i : tree[num]) {
            if(!visited[i]) {
                result[i] = num; // DFS 탐색하면서 부모 노드를 정답 배열에 저장
                DFS(i);
            }
        }
    }
}