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

문제

11725번: 트리의 부모 찾기

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

입력

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

출력

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

접근방식

입력 조건을 보면 노드의 개수가 2에서 100,000개인 것에 유의해야한다. 인접 행렬이 아닌 인접리스트로 풀어야한다는 생각으로 시작한다. 무방향 그래프이기 때문에 양쪽에 서로 추가해주면 된다. 

static ArrayList<Integer>[] graph = new ArrayList[n+1];

for(int i=1;i<=n;i++){
    graph[i] = new ArrayList<>();
}

for(int i=0;i < n-1;i++){
    int a = scanner.nextInt();
    int b = scanner.nextInt();
    graph[a].add(b);
    graph[b].add(a);
}

부모 노드 번호를 출력해야하고 트리의 루트를 1로 정한다고 했기 때문에 DFS로 구현할 경우 1번부터 인접리스트를 따라 가면서 체크여부를 갱신하면서 부모 노드값을 넣어주면 된다. idx값으로 연결된 리스트 들의 값은 idx를 부모 노드로 가지는 자식 노드임을 알고 구현하면 됩니다. 

static int[] parentNodes;
static boolean[] check;

public static void DFS(int idx){
    for(int x : graph[idx]) {
        if(!check[x]) {
            check[x] = true;
            parentNodes[x] = idx;
            DFS(x);
        }
    }
}

풀이

import java.util.*;

public class Main {
    static int n;
    static ArrayList<Integer>[] graph;
    static int[] parentNodes;
    static boolean[] check;

    public static void DFS(int idx){
        for(int x : graph[idx]) {
            if(!check[x]) {
                check[x] = true;
                parentNodes[x] = idx;
                DFS(x);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        graph = new ArrayList[n+1];
        parentNodes = new int[n+1];
        check = new boolean[n+1];
        StringBuilder sb = new StringBuilder();

        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0;i < n-1;i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }
        
        DFS(1);
        
        for(int i=2;i<=n;i++){
            sb.append(parentNodes[i]+"\n");
        }
        System.out.print(sb);
    }
}