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

접근

입력값은 불규칙적으로 입력되기 때문에 일단 트리의 간선 정보를 저장해둔 후 처리할 필요가 있다. 나는 Node 클래스를 만들어 연결된 다른 노드들을 저장하도록 했다. 그리고 1번, 즉 루트 노드부터 시작해서 연결된 노드들을 큐에 넣어가며 부모 정보를 저장했다. 

 

근데 생각보다 실행 시간이 오래 걸려서 다른 사람들의 코드를 참고했더니, 알고리즘은 동일하고 StringBuilder/StringBuffer 를 사용하는 것 같았다. 출력 부분만 수정해서 재채점해본 결과 시간을 1/4로 줄일 수 있었다. 참고로, 둘의 차이점은 동기화의 유무로 알고리즘 레벨에서는 구분짓지 않고 사용해도 괜찮을 것 같다. 

 

코드

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

public class BJ11725 {
    static class Node{
        int num;
        ArrayList<Node> childs;

        Node(int num){
            this.num = num;
            this.childs = new ArrayList<>();
        }

        void add(Node node){
            this.childs.add(node);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuffer sb = new StringBuffer();

        int n = Integer.parseInt(br.readLine());
        Node[] tree = new Node[n+1];
        for (int i = 1; i <= n; i++)
            tree[i] = new Node(i);

        // 입력값 저장
        for (int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            tree[a].add(tree[b]);
            tree[b].add(tree[a]);
        }

        // 부모 찾기
        int[] parent = makeTree(tree);

        // 결과값 출력
        for (int i = 2; i <= n; i++)
            sb.append(parent[i]).append("\n");

        System.out.println(sb);
    }

    private static int[] makeTree(Node[] tree) {
        int[] parent = new int[tree.length];
        Queue<Node> q = new LinkedList<>();

        parent[1] = 1; // 1번 노드가 루트임
        q.add(tree[1]);
        
        while(!q.isEmpty()){
            Node cur = q.poll();

            for(Node child : cur.childs){
                if(child.num == cur.num || parent[child.num] != 0) continue;

                parent[child.num] = cur.num;
                q.add(child);
            }
        }

        return parent;
    }
}