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

문제

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

---

입력

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

출력

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

---

예제 입력 1

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

예제 출력 1

4
6
1
3
1
4

---

트리의 루트는 항상 1로 고정되어 있고 2번 노드부터 부모 노드를 출력하니 출발지는 1로 둔다.

 

트리의 부모를 저장하는 배열을 하나 두고 0으로 초기화한다.

 

양방향 연결 리스트를 만들어 from - to 형식으로 추가를 해 준다.

 

1부터 시작해서 1의 자식노드를 전부 돌아서 트리의 부모를 젖아하는 배열에 값이 아직 안들어있을때 부모 노드로 값을 저장한 후 큐에 넣어준다.

 

기본적인 BFS 문제이다.

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main11725 {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static ArrayList<ArrayList<Integer>> list;
    public static int[] ans;
    public static void main(String[] args) throws Exception {
        int N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        for(int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        ans = new int[N + 1];
        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());
            list.get(from).add(to);
            list.get(to).add(from);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        ans[1] = -1;
        while(!queue.isEmpty()) {
            int current = queue.poll();

            for(int next : list.get(current)) {
                if(ans[next] == 0) {
                    ans[next] = current;
                    queue.add(next);
                }
            }
        }
        for(int i = 2; i <= N; i++) {
            bw.write(Integer.toString(ans[i]));
            bw.newLine();
        }
        br.close();
        bw.flush();
        bw.close();
    }
}