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

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

11725번: 트리의 부모 찾기

처음에 문제 이해를 잘 못했었다.

정확히 무엇을 출력해야하는 것인지를 이해하지 못했었는데

알고보니 노드 2번부터 N번까지 차례대로 부모노드가 몇번인지를 알려달라는 것 이었다.

 

dfs를 적용하면 간단하게 해결할 수 있던 문제였다.

 

트리의 루트가 1번이기 때문에 dfs로 1번부터 순차적으로 방문을 체크하면서 확인해주면 된다.

import java.util.*;
import java.io.*;

class Main{
    static boolean[] visited;
    static int[] parent;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        visited = new boolean[N+1];
        parent = new int[N+1];
        
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        for(int i=0; i<N+1 ; i++){
            lists.add(new ArrayList<>());
        }
        for(int i=0 ; i<N-1 ; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            
            lists.get(a).add(b);
            lists.get(b).add(a);
        }
        
        dfs(1, lists);
        
        for(int i=2;i<N+1 ; i++){
            System.out.println(parent[i]);
        }
    }
    public static void dfs(int index, ArrayList<ArrayList<Integer>> lists){
        visited[index] = true;
        for(int i : lists.get(index)){
            if(!visited[i]){
                parent[i] = index;
                dfs(i,lists);
            }
        }
    }
    
}