백준 11725번 : 트리의 부모 찾기 java

이 문제는 루트 노드가 정해져 있으니 루트 노드로부터 시작하여 간선들을 bfs를 이용하여 만나는 노드들을 조건에 맞게탐색하는 문제입니다.

저는 이 문제를 해결하기 위해 N개의 ArrayList<Integer>를 List<ArrayList<Integer>>안에 넣어서 각각의 자리를 노드의 시작점으로 사용하였습니다.

그리고 1번 노드가 루트 노드이니 루트 노드에서 시작하여 연결된 간선들에 부모 노드를 입력하면서 진행하였습니다.

코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static List<List<Integer>> l;
    static int[] answer;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        answer = new int[N+1];

        l = new ArrayList<>();
        for(int i = 0; i<=N; i++)
            l.add(new ArrayList<>());

        for(int i = 0; i<N - 1; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            l.get(from).add(to);
            l.get(to).add(from);
        }

        bfs();

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

    }

    static void bfs(){
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);

        while(!q.isEmpty()){
            int num = q.poll();

            for(int i = 0; i<l.get(num).size(); i++){
                int next = l.get(num).get(i);

                if(answer[next] == 0){
                    answer[next] = num;
                    q.offer(next);
                }
            }
        }
    }
}