[Baekjoon] 11725번 트리의 부모 찾기 (Java)

예제 입력1

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력1

4
6
1
3
1
4

 

 

예제 입력2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력2

1
1
2
3
3
4
4
5
5
6
6

 

 

package Q11725;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static ArrayList<ArrayList<Integer>> arr;
    static int[] parent;

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

        arr = new ArrayList<>();
        for(int i = 0; i<=num; i++)
        	arr.add(new ArrayList<>());

        for(int i = 0; i<num - 1; i++){
            String[] st = br.readLine().split(" ");

            int from = Integer.parseInt(st[0]);	
            int to = Integer.parseInt(st[1]);

            arr.get(from).add(to);		// 인덱스 from에 to 추가
            arr.get(to).add(from);		// 인덱스 to에 from 추가
        }
        bfs();
        for(int i = 2; i<=num; i++)
            System.out.println(parent[i]);
    }

    static void bfs(){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        // offer() 삽입
		// remove() = poll() 삭제
		// element() = peek() 맨앞

        while(!queue.isEmpty()){
            int num = queue.poll();		// pop

            for(int i = 0; i < arr.get(num).size(); i++){	// 인덱스num의 크기만큼 반복(연결된 노드 수)
                int next = arr.get(num).get(i);				// next: arr의 인덱스 num에 있는 것 중에 인덱스 i번째 있는 수
                if(parent[next] == 0){						// parent 배열 인덱스 next에 아무것도 없다면
                	parent[next] = num;						// num 추가
                	queue.offer(next);						// 큐에 next 삽입
                }
            }
        }
    }
}