[백준] 11725 트리의 부모 찾기(Java)

문제링크

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

문제분석

• 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
• 노드의 연결 관계를 표현하기 위해 연결 리스트 사용 : N<=100,000 이므로 이차원 배열을 선언하면 메모리가 초과된다.
• 노드를 입력 받을 때는, 부모 자식 간 구분이 없으므로 양방향으로 저장한다.

입력

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

출력

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

풀이

• 큐를 이용해 루트노드(1번 노드)부터 탐색을 해나간다. 현재 노드와 연결된 노드들은 부모 or 자식 노드이다.
• 탐색 시, 이미 방문한 노드가 나오면 현재 노드의 부모노드이므로 넘어간다.
• 탐색 시, 방문한적이 없다면 자식노드이다.

전체 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        //연결리스트 선언
        ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
        for (int i = 0; i <= n; i++) tree.add(new ArrayList<Integer>());

        //출력에 사용할 부모노드 선언
        int[] parent = new int[n+1];
        //탐색에 사용할 체크 배열 선언
        boolean[] ch = new boolean[n+1];

        //부모 자식간 구분없이 입력이 들어온다. 따라서 양방향으로 입력 받는다.
        for(int i=0; i<n-1; i++){
            int node1 = scanner.nextInt();
            int node2 = scanner.nextInt();

            tree.get(node1).add(node2);
            tree.get(node2).add(node1);
        }

        //큐를 이용해 탐색 진행
        Queue<Integer> queue = new LinkedList<>();

        //가장 먼저 루트 노드(1번)을 큐에 넣는다.
        ch[1] = true;
        queue.offer(1);

        while(!queue.isEmpty()){
            //현재 노드가 부모 노드. 이전에 탐색 된적이 없기 때문이다.
            Integer parentNode = queue.poll();

            //자식 노드를 탐색한다.
            for (Integer connectedNode : tree.get(parentNode)) {
                //이미 방문했다면, 자식 노드가 아니다.
                if(ch[connectedNode]) continue;
                else{
                    //자식 노드라면,
                    //재방문을 막기 위해 방문을 체크한다.
                    ch[connectedNode] = true;
                    //자식 노드의 부모노드 저장
                    parent[connectedNode] = parentNode;
                    //자식 노드를 큐에 넣는다.
                    queue.add(connectedNode);
                }
            }
        }

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