코딩 테스트 풀이 18 - 트리의 부모 찾기

✔ 문제

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

💡 접근 방법

1. Parent 정보를 담을 배열과 양방향 Edge 정보를 담을 Arraylist를 초기화 한 후 입력되는 정보를 담고,
2. Deque을 사용해 현재 노드와 연결된 노드들이 parent 가 없을 시 현재 노드로 parent로 저장하고, 해당 노드들을 다시 deque에 담는 식으로 구현하였다.

⭐ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int nodeNum = Integer.parseInt(br.readLine());

        // Initialize Node Parent Array
        int[] parent = new int[nodeNum+1];

        // Edge 초기화 , 1+하는 이유는 Node 를 0이 아니라 1부터 시작하고 싶어서
        ArrayList<Integer>[] Edges = new ArrayList[nodeNum+1];
        for (int i = 1; i < nodeNum + 1 ; ++i)
        {
            Edges[i] = new ArrayList<>();
        }

        // Edge Initialize
        for (int i = 0; i < nodeNum - 1; ++i)
        {
            String[] strArr = br.readLine().split(" ");

            int num1 = Integer.parseInt(strArr[0]);
            int num2 = Integer.parseInt(strArr[1]);
            Edges[num1].add(num2);
            Edges[num2].add(num1);
        }

        Deque<Integer> queue = new ArrayDeque<>();

        // 루트 노드
        queue.addLast(1);

        while(!queue.isEmpty())
        {
            int cur = queue.pollFirst();
            for (int child : Edges[cur])
            {
                if (parent[child] != 0)
                    continue;

                parent[child] = cur;
                queue.addLast(child);
            }
        }

        for (int i = 2; i < parent.length; ++i)
        {
            System.out.println(parent[i]);
        }
    }
}