[JAVA] 백준 q11725 - 트리의 부모 찾기

11725번: 트리의 부모 찾기

---

> 의식의 흐름

 

> 풀이 과정

1. 연결된 노드 담기

2. 1번 노트부터 시작 (트리의 루트를 1이라고 정했기 때문)

3. 현재 노드(nowIdx)와 연결된 노드들의 부모 설정하기 (parents[])

4. 2번 노드부터 부모 출력

 

> 코드

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

public class Main {
    public static int N; // 노드의 개수
    public static ArrayList<ArrayList<Integer>> links = new ArrayList<>(); // 연결된 노드 담기
    public static boolean[] visited;
    public static int[] parents;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        for(int i=0;i<=N;i++){
            links.add(new ArrayList<Integer>());
        }

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

            links.get(a).add(b);
            links.get(b).add(a);
        }

        // 부모 찾기
        visited = new boolean[N+1];
        parents = new int[N+1];
        findParents(1, 1);

        for(int i=2;i<=N;i++){
            bw.write(Integer.toString(parents[i])+"\n");
        }
        bw.flush();

        br.close();
        bw.close();
    }

    public static void findParents(int nowIdx, int parentIdx){
        visited[nowIdx] = true;
        parents[nowIdx] = parentIdx;

        for(int i:links.get(nowIdx)){
            if(!visited[i])
                findParents(i, nowIdx);
        }
    }
}