[JAVA] 백준 11725 트리의 부모 찾기_트리

 

문제 : 

https://www.acmicpc.net/problem/11725

 

 

접근 : 

 

  - 입력되는 정보로 그래프를 작성

 

  - 루트가 1 이므로 DFS를 통하여 1부터 인접한 노드의 부모 노드를 현재 수로 등록한다.

 

  - 만약 인접 노드가 자신의 부모 노드일 경우 DFS를 실행하지 않는다.

 

  - 부모 노드를 모두 등록하면 2부터 자신의 부모 노드를 출력한다.

 

 

 

 코드 구현 : 

 

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

public class Main {
    private static ArrayList<Integer>[] adj;
    private static int[] parents;

    static void dfs(int now){
        for(int n : adj[now]){
            if(parents[now] == n) continue;
            parents[n] = now;
            dfs(n);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        String[] inputs;
        adj = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();

        parents = new int[n+1];
        int a, b;

        for(int i = 1 ; i < n ; i++) {
            inputs = br.readLine().split(" ");
            a = Integer.parseInt(inputs[0]);
            b = Integer.parseInt(inputs[1]);
            adj[a].add(b);
            adj[b].add(a);
        }
        dfs(1);
        for(int i = 2; i <= n ; i++) sb.append(String.format("%d%n", parents[i]));
        System.out.println(sb);
        br.close();
    }
}